1105. One Slot Each, Most Profit

Each job takes exactly one time slot. Slots are numbered 1, 2, 3 and so on, and only one job runs per slot. Job i has a DEADLINE d and a PROFIT p, and earns its profit only if it is placed in a slot numbered d or lower.

Print the largest total profit obtainable.

jobs (d=2,p=100) (d=1,p=19) (d=2,p=27) (d=1,p=25) -> 127 jobs (d=1,p=5) (d=1,p=6) (d=1,p=7) -> 7 jobs (d=3,p=1) (d=3,p=1) (d=3,p=1) -> 3

Trace the first line. Only two slots are usable, since no deadline is above 2. The richest two jobs are the ones worth 100 and 27, and both have deadline 2, so they can sit in slots 1 and 2 in either order. Total 127. The job worth 25 loses out even though it is worth more than the job worth 19, because both of those are shut out entirely.

## What most people try first

Sorting by DEADLINE and taking greedily. That ignores profit completely and answers 46 on the first example, taking the two deadline-1 jobs first.

Sorting by PROFIT descending and placing each job in the latest free slot at or before its deadline is CORRECT, and it needs a structure to find "the latest free slot at or before d" quickly. A plain scan makes it O(n * maxD), which at 200000 jobs and deadlines to 10^9 is not even representable as an array.

Trying every subset is 2^n.

## The method

Sort by DEADLINE ascending and carry a min-heap of the profits accepted so far.

sort jobs by deadline ascending heap = empty min-heap of profits for (d, p) in that order: push p if size of heap > d: pop the smallest answer = the total of everything left in the heap

One sort and n heap operations, O(n log n). The heap never holds more than n entries and deadlines never need to be materialised as slots, so deadlines up to 10^9 cost nothing.

## Why the heap rule is correct

The invariant is: after processing every job with deadline at most D, the heap holds a set of jobs that (a) can all be scheduled legally and (b) has the largest total profit among all legal sets drawn from those jobs.

Feasibility first. A set of jobs sorted by deadline is schedulable exactly when the jth of them, counting from 1, has deadline at least j. Processing in deadline order and capping the heap size at d maintains precisely that, because when the current deadline is d the heap may hold at most d jobs and every one of them has deadline at most d.

Optimality second. Suppose the heap is full at d and a new job arrives. If the new job is worth more than the cheapest job in the heap, swapping them keeps the set the same size, so it is still feasible, and raises the total. If it is worth less, adding it would force out something better, so it is dropped. Either way the invariant is restored by exactly one comparison, which is what the heap performs.

This is an exchange argument run online: the heap IS the current optimal set, and each arrival either improves it by one swap or does not belong.

## The boundary that breaks a careless implementation

The cap is size > d, not size > d - 1 and not size >= d. With one job of deadline 1 the heap may hold exactly one job, so nothing is evicted, and a wrong comparison reports 0.

Profits of 0 are allowed. A job worth nothing can still be accepted and then evicted, and that is harmless; a solution that skips zero-profit jobs entirely also gets the right answer, which is worth noticing rather than relying on.

Deadlines are not slot indices to be allocated. Nothing in the method ever builds an array of slots, and doing so is the usual way this solution becomes too slow.

## Sizes

n reaches 2 * 10^5 and each profit reaches 10^9, so the total reaches 2 * 10^14. That is far past the 2147483647 limit of a signed 32-bit integer, and five jobs worth 10^9 already give 5 * 10^9, which is what the ninth test checks. The heap SIZE is at most n and fits in 32 bits.

## A related problem

Problem #1106 is the same eviction pattern with the profits removed and the durations made variable: there every job takes a different amount of time, all profits are equal, and the heap evicts the LONGEST job rather than the cheapest one. Comparing the two is the fastest way to see what the heap is really doing.

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