923. How Many Courses You Can Finish
Course i takes t[i] continuous days and must be FINISHED on or before day
d[i]. You start on day 1 and take courses one at a time, never overlapping and
never pausing one to start another. Print the largest number of courses you can
finish.
``` courses (t=100,d=200) (t=200,d=1300) (t=1000,d=1250) (t=2000,d=3200) -> 3 take the 100 (done day 100), the 200 (done day 300), the 1000 (done day 1300, too late) ... so instead take the 100, the 1000 and the 200, finishing on days 100, 1100 and 1300.
one course (t=5,d=3) -> 0 it cannot be finished in time courses (t=1,d=1) (t=2,d=2) -> 1 ```
## What most people try first
Sorting by duration and taking the shortest first ignores deadlines. Sorting by deadline and taking greedily until one fails is wrong too, because a long course taken early can block several short ones later.
Trying every subset is 2^n, and for each subset the order that works, if any,
is deadline order. At n = 30 that is 1.07 * 10^9 subsets.
## The method
Sort by deadline. Take every course as you meet it. When the running total passes the current deadline, give back the LONGEST course taken so far, which may well be the one just taken.
sort courses by deadline ascending
h = empty max-heap of durations, total = 0
for (t, d) in that order:
push t onto h; total = total + t
if total > d:
total = total - pop the largest duration from h
print size(h)
## Why it is correct
First, a set of courses can be completed exactly when, taken in deadline order, every prefix total is at most that prefix's last deadline. Deadline order is optimal for any fixed set by the standard swap: if two adjacent courses are out of deadline order, exchanging them cannot make either miss, since the later deadline has more room.
Now the exchange argument for the greedy. Maintain the invariant that after
processing the courses with the j smallest deadlines, the heap holds a
LARGEST possible feasible subset of them, and among all largest feasible
subsets it has the SMALLEST total duration.
Adding a course keeps feasibility if the total still fits. If it does not, the set must shed one course, and dropping the longest is best: it reduces the total the most, so the remaining set has the smallest total of any set of that size, and a smaller total can never make a later course infeasible when a larger one would not.
Note the size never decreases, because one course is added and at most one removed. So the heap size at the end is the largest feasible count.
## The boundary that breaks a careless implementation
The comparison is total > d, not >=. Finishing exactly on the deadline day
is allowed, and using >= loses a course on every input that just fits.
A course with t > d can never be taken alone or otherwise. The algorithm
handles it without a special case: it is pushed, the total exceeds d, and it
is itself the longest, so it is immediately given back.
Sorting by duration instead of deadline breaks the feasibility test that the single comparison stands in for.
## Overflow
total is the sum of the durations currently held. It is bounded by the
largest deadline, which is 2 * 10^9, EXCEPT at the moment just after a push
and before the pop: there it can reach a deadline plus one duration, so
2 * 10^9 + 10^9 = 3 * 10^9. A signed 32-bit integer holds 2147483647, so that
intermediate value overflows.
This matters and it is easy to miss: the declared test with three courses of
duration 10^9 and deadline 2 * 10^9 computes a true total of 3 * 10^9
which a 32-bit build wraps to -1294967296. That is less than the deadline, so
no course is given back and the answer comes out 3 instead of 2. Hold total
in 64 bits.
## Related problems
Problem #904 also pairs deadlines with a heap and an exchange argument, and the two differ in exactly one place: there every job takes ONE unit, so feasibility is a count per deadline and the heap holds profits to be maximised. Here the durations vary, so feasibility is a running total and the heap holds durations to be minimised. Solving one and assuming the other works the same way is the mistake the pair exists to prevent.
## Cost
Time O(n log n). Space O(n).
Constraints - `1 ≤ n ≤ 100000` - `1 ≤ t[i] ≤ 10^9` - `1 ≤ d[i] ≤ 2000000000`
Input
The first line contains an integer n.
Each of the next n lines contains two integers: the duration of one course and the day by which it must be finished.
Output
Print one integer on its own line: the largest number of courses that can be finished, taking them one at a time from day 1. No other text.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.