1106. The Most Jobs Finished On Time

One machine starts at time 0. Job i takes p units of work and must FINISH by time d. You may refuse jobs; the ones you accept run back to back in an order you choose, with no idling.

Print the largest number of jobs that can all finish on time.

jobs (100,200) (200,1300) (1000,1250) (2000,3200) -> 3 jobs (5,4) -> 0 jobs (4,4) -> 1 jobs (9,10) (2,11) (3,12) (1,13) (4,14) -> 4

Trace the last line. Taking everything means finishing at 9, 11, 14, 15, 19, and the third job is already late at 14 against a due time of 12. Drop the nine-unit job and the rest finish at 2, 5, 6, 10 against 11, 12, 13, 14, all comfortable. Four jobs.

## What most people try first

Taking the SHORTEST jobs first, ignoring deadlines. On (1,1) (2,100) (3,100) that takes all three and they finish at 1, 3, 6, all on time, so it looks fine. On (5,5) (1,1) (1,100) shortest-first takes (1,1) finishing at 1, then (1,100) finishing at 2, then (5,5) finishing at 7, which is late, so it reports 2. The true answer is also 2, so that does not separate them either. The honest separator is that shortest-first has no eviction step: once it accepts a job it can never change its mind, and the rule below can.

Taking jobs in deadline order and accepting whatever fits is closer and still wrong. On (9,10) (2,11) (3,12) (1,13) (4,14) it accepts the nine-unit job because it fits on its own, then cannot fit the 3, giving 4 as well by luck; on (7,8) (4,9) (5,15) (2,16) (6,20) (1,21) the same rule accepts 7 then 4 is late at 11 against 9, and it ends with fewer than the 5 that are possible. That input is in the tests.

Trying every subset is 2^n.

## The method

Process in order of DEADLINE and keep the accepted jobs in a MAX-heap keyed by duration.

sort jobs by d ascending heap = empty max-heap of durations clock = 0 for (p, d) in that order: push p, clock = clock + p if clock > d: clock = clock - (pop the largest duration) answer = the number of entries in the heap

One sort and n heap operations, O(n log n).

## Why evicting the LONGEST job is correct

The invariant is: after processing every job with deadline at most D, the heap holds a feasible set of the largest possible size drawn from those jobs, and among all such largest sets it has the smallest total duration.

Feasibility. A set of jobs is schedulable on one machine exactly when, run in deadline order, no prefix total exceeds the deadline of its last job. The clock tracks precisely that prefix total.

The step. A new job arrives and is provisionally accepted. If the clock is still within d, the set grew by one and is still feasible, so both halves of the invariant hold, the second because the new total is forced.

If the clock passed d, no set of that size drawn from these jobs is feasible, because the invariant says the previous set already had the smallest possible total for its size, and adding one more job to any set of that size gives a total at least as large. So the size must go back down by one, and the question is only which job to drop. Dropping the LONGEST one leaves the smallest possible total, which is exactly the second half of the invariant, and a smaller total can only help every job still to come, since their deadlines are all at least d.

That is the exchange: any other job could be dropped instead, but swapping the dropped job for the longest one leaves a set of the same size and a total that is no larger, so nothing is lost.

## The boundary that breaks a careless implementation

The test is clock > d, not >=. A job finishing exactly on its due time is on time, and the strict comparison reports 0 for the single job (4,4).

The newly arrived job must be pushed BEFORE the check, because it may itself be the longest and be the one evicted. A solution that checks first and pushes second cannot reject a huge job that arrives last.

Jobs of duration 0 are legal and always fit.

## Sizes

n reaches 2 * 10^5 and p reaches 10^9, so the clock reaches 2 * 10^14, well past the 2147483647 limit of a signed 32-bit integer. The eighth test uses four jobs of 10^9 against a deadline of 4 * 10^9: in 64 bits all four are on time, and a 32-bit clock wraps negative partway through and gets it wrong.

## Related problems

Problem #1105 uses the same eviction shape with the roles reversed: there every job takes one slot and carries a profit, and the heap throws away the CHEAPEST. Problem #1104 keeps every job and minimises the worst lateness instead, which needs no heap at all.

Constraints - `1 ≤ n ≤ 200000` - `0 ≤ p ≤ 1000000000` - `0 ≤ d ≤ 1000000000000`