MSCHED  Milk Scheduling
English  Vietnamese 
Farmer John has N cows that need to be milked (1 <= N <= 10,000), each of which takes only one unit of time to milk.
Being impatient animals, some cows will refuse to be milked if Farmer John waits too long to milk them. More specifically, cow i produces g_i gallons of milk (1 <= g_i <= 1000), but only if she is milked before a deadline at time d_i (1 <= d_i <= 10,000). Time starts at t=0, so at most x total cows can be milked prior to a deadline at time t=x.
Please help Farmer John determine the maximum amount of milk that he can obtain if he milks the cows optimally.
Input :
 Line 1: The value of N.
 Lines 2..1+N: Line i+1 contains the integers g_i and d_i.
Output : A single numbers denotes the maximum number of gallons of milk Farmer John can obtain.
Sample :
Input:
4
10 3
7 5
8 1
2 1
Output :
25
Input details : There are 4 cows. The first produces 10 gallons of milk if milked by time 3, and so on.
Output details : Farmer John milks cow 3 first, giving up on cow 4 since she cannot be milked by her deadline due to the conflict with cow 3. Farmer John then milks cows 1 and 2.
hide comments
mahilewets:
20170902 06:37:58
Many WA's


nadstratosfer:
20170823 05:17:17
WA with an algo too simple to debug.. Can't stand the unavailability of testcases :( 

singhsauravsk:
20170422 22:34:35
Implementation of Job Sequencing Problem. 

Mayank Garg:
20161218 07:50:52
400th AC :D though a silly mistake resulted in WA :P 

deerishi:
20161003 03:10:10
nlogn!! Priority queues <3 ! 

partha2717:
20160520 12:59:09
AC at last... 

pbd:
20160223 17:48:30
Read CLRS ed. 3 section 16.5 to solve this problem. A very famous task scheduling problem. 

ashish kumar:
20150105 10:46:27
wrong ans on 10th testcase 

Siarhei Khamenka:
20140627 00:32:43
So as I understand it cannot be solved in something different from C/C++?


radko:
20140401 11:24:47
i have a O((d + N) log N) solution but it fails with TLE, is there a faster way?

Added by:  Kata 
Date:  20140312 
Time limit:  0.100s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  USACO Dec 13, Silver Div 