899. The Order the Single Machine Runs Them

One machine processes n jobs. Job i, numbered from 0 in input order, becomes available at time a and takes d units to run. The machine runs one job at a time and never interrupts a job once it has started.

Whenever the machine is free it takes the SHORTEST available job; on a tie it takes the one with the smaller index. If nothing is available it stays idle until the next job becomes available, and then chooses among everything available at that instant.

Print the job indices in the order they are run.

(1,2) (2,4) (3,2) (4,1) -> 0 2 3 1 (10,1) (0,1) (5,1) -> 1 2 0 (0,9) (1,1) (2,1) (3,1) (4,1) -> 0 1 2 3 4

Trace the first one. The machine is idle until time 1, when job 0 becomes available, and runs it until time 3. At time 3 jobs 1 and 2 are available with durations 4 and 2, so job 2 runs until time 5. At time 5 jobs 1 and 3 are available with durations 4 and 1, so job 3 runs until time 6. Then job 1.

The third row shows why the availability test matters: job 0 starts at time 0 because it is the only thing available, and it holds the machine until time 9, by which point everything else has arrived and they run in index order because they all take 1.

## What most people try first

Sorting by duration and running in that order. Wrong, because a short job that has not arrived yet cannot be run. The second example has three jobs of duration 1, so a duration sort broken by index gives 0 1 2 while the answer is 1 2 0: job 0 does not exist until time 10.

Sorting by arrival and running in that order. Also wrong, because it never looks at the durations. On the first example it gives 0 1 2 3 while the answer is 0 2 3 1.

Scanning every unfinished job at each step. Correct, and O(n) per step for O(n^2) overall, which is 4 * 10^10 at the limits.

## Two structures, one clock

The jobs must be sorted by ARRIVAL, so that they can be released into the pool in time order with a pointer that only moves forward. The pool itself must be ordered by DURATION, so that the shortest is available in O(log n).

sort the jobs by (arrival, ...) and keep a pointer p at the first unreleased one h = min-heap ordered by (duration, index) clock = 0 while some job has not run: if h is empty and the next job arrives later than clock: clock = that arrival time (the machine idles) release every job whose arrival is at most clock into h (dur, i) = pop h clock = clock + dur output i

## Why the clock jump is the whole problem

Two different things advance the clock and they must happen in the right order. Running a job advances it by the duration. Idling advances it to the next arrival, and that may only happen when nothing is available.

Jumping the clock when the heap is NOT empty is the common bug: it skips past jobs that were already runnable and changes the order. Failing to jump when the heap IS empty leaves the loop spinning forever, or releases nothing and pops an empty heap.

The release loop must also come AFTER the possible jump, since the jump is precisely what makes the next job releasable.

## Why sorting by arrival does not conflict with choosing by duration

Sorting is used only to decide the ORDER OF RELEASE, and it is never used to choose what to run. Once released, a job's arrival time stops mattering entirely, which is why the heap key is the duration alone (plus the index for the tie). Keeping the two roles separate is the idea that transfers: one ordering to feed the structure, another inside it.

## The tie rule

Equal durations are broken by the smaller index, so the heap key is the pair (duration, index). Without it, 0 1 and 1 0 would both be defensible on two identical jobs and the judge could not mark either.

## Overflow, with the actual magnitude

Arrivals reach 10^10 and are already outside a signed 32-bit integer, whose ceiling is 2147483647. A 32-bit build truncates an arrival of 3 * 10^9 to a NEGATIVE number, which makes that job look available at time 0 and changes the output order outright. The test with an arrival of 3000000000 is exactly that case: the correct answer is 0 2 1 and a 32-bit build prints 1 0 2.

The clock is worse still: 10^10 plus two hundred thousand durations of 10^9 reaches about 2.1 * 10^14.

## Related problems

Problem 893 is this problem with every arrival at 0, where the whole set is known up front, a single sort gives the optimal order, and the heap is pointless. That pair is the cleanest illustration in this block of what a heap is actually for. Problem 885 fixes the order of the jobs and lets the MACHINES be chosen, which puts the machines in the heap instead.

## Cost

Time O(n log n). Space O(n).

Constraints - `1 ≤ n ≤ 200000` - `0 ≤ a ≤ 10000000000` - `1 ≤ d ≤ 1000000000`