904. The Jobs You Can Fit Before Their Deadlines
Each of n jobs takes exactly one unit of time, pays a profit, and has a
DEADLINE: the job earns its profit only if it is finished by the end of that
time unit. One machine runs one job per unit, starting at unit 1.
Print how many jobs you run and the largest total profit, in that order.
``` (deadline 2, profit 100) (1, 19) (2, 27) (1, 25) -> 2 127 run the 25 in unit 1 and the 100 in unit 2
(1, 5) (1, 7) (1, 9) -> 1 9 three jobs all want unit 1, so only the 9 survives
(3, 1) (2, 2) (1, 3) -> 3 6 one job per unit and everything fits ```
## What most people try first
Sort by profit descending and, for each job, scan backwards from its deadline
for a free unit. That is correct, and it is O(n * d) in the worst case: with
n = 200000 jobs all carrying deadline 200000, the scan for the last job walks
the whole timetable, so the total is around 2 * 10^10 steps.
A union-find over the time units repairs the scan. This problem is here for the other repair, the one that needs no extra structure at all.
## The method
Sort by DEADLINE ascending instead, and carry a min-heap of the profits of the jobs currently accepted.
sort jobs by deadline ascending
h = empty min-heap
for (d, p) in jobs:
push p onto h
if size(h) > d:
pop the smallest profit off h
answer = size(h), and the total of what is left in h
The invariant is that after processing every job with deadline at most d, the
heap holds a set of size at most d with the largest total achievable from
those jobs. The heap is not choosing anything clever; it is answering "which of
my accepted jobs is the one I would give up first".
## Why it is correct
Two facts do the work.
First, a set of jobs is schedulable exactly when, for every t, the number of
chosen jobs with deadline at most t is at most t. If that holds, sorting the
chosen jobs by deadline and running them in that order finishes each one in
time; if it fails for some t, then more than t jobs need the first t units
and no order can help.
Second, the exchange argument. Suppose the heap currently holds the best set of
size k for the jobs seen so far, and a new job with profit p arrives. If the
set is still schedulable after adding it, adding it can only help, because
profits are positive. If it is not, then one job must go, and dropping the
SMALLEST profit is at least as good as dropping any other: take any optimal
solution for this prefix, and if it excludes a job the heap keeps while
including one the heap dropped, swapping the two keeps the size the same, keeps
schedulability (same count per deadline), and does not lower the total.
That is the whole proof, and it is why the answer is found without ever deciding which unit a job actually runs in.
## The boundary that breaks a careless implementation
The comparison is size(h) > d, not >=. A job with deadline 3 may share the
timetable with two others of deadline at most 3, so three accepted jobs is
legal and four is not. Writing >= silently throws away one job per deadline
and the count comes out short on every input.
The other trap is the sort key. Sorting by profit and using a max-heap looks symmetric and is wrong: the feasibility test above is stated per deadline, so the jobs have to arrive in deadline order for the size check to mean anything.
## Overflow
2 * 10^5 jobs at 10^9 profit each total 2 * 10^14. That is far past
2147483647, and a 32-bit accumulator wraps to a value that can even be
negative. The declared test with five jobs of 10^9 reaches 5 * 10^9 and
breaks a 32-bit build on its own. Use 64 bits for the total; the COUNT is at
most 2 * 10^5 and needs nothing special.
## Related problems
Problem #468 also chooses a non-conflicting set of jobs for the most profit, but its jobs have a start and an end and occupy a whole interval, so the choice is made by a dynamic program over end times. Here every job takes one unit and only the deadline matters, which is what makes the heap greedy available. Problem #1036 takes the most meetings rather than the most profit and needs no heap at all, because with equal value the earliest finish always wins.
## Cost
Time O(n log n), dominated by the sort. Space O(n).
Constraints - `1 ≤ n ≤ 200000` - `1 ≤ deadline ≤ 200000` - `1 ≤ profit ≤ 10^9`
Input
The first line contains an integer n.
Each of the next n lines contains two integers: the deadline and the profit of one job.
Output
Print two integers on one line, separated by a single space: how many jobs are run, then the largest total profit. No other text.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.