913. The Order the Single Processor Finishes In
n tasks are numbered 0 to n-1. Task i becomes AVAILABLE at time t[i]
and needs d[i] units of processor time. One processor runs one task at a time
and never interrupts a running task. Whenever it is idle:
if some task is available, run the one with the SMALLEST duration,
breaking ties by the smaller index
otherwise jump the clock forward to the next availability time
Print the task indices in the order they are run.
``` tasks (t=1,d=2) (t=2,d=4) (t=3,d=2) (t=4,d=1) -> 0 2 3 1 clock jumps to 1 and runs task 0 until 3; tasks 1 and 2 are now available and task 2 is shorter, so it runs until 5; task 3 is now available and is shortest, so it runs until 6; task 1 runs last
single task (t=5,d=3) -> 0
three tasks all (t=10,d=1) -> 0 1 2 ```
## What most people try first
Sorting by availability and running in that order ignores the rule entirely.
Sorting by duration ignores availability: a very short task that only appears
at time 10^9 cannot be run first.
Re-scanning all n tasks for the best available one before each of the n
runs is correct and costs O(n^2). At n = 10^5 that is 10^10 comparisons.
## The method: one sorted pass plus one heap
The availability times and the durations are two different orders, so use two structures for them.
sort tasks by availability time, remembering the original index
h = empty min-heap ordered by (duration, index)
time = 0, i = 0
while some task remains:
push every task whose availability is <= time; advance i past them
if h is empty:
time = availability of task i (jump forward, push nothing yet)
continue
(dur, idx) = pop h
time = time + dur
output idx
The sorted array answers "what has become available by now"; the heap answers "of those, which is shortest". Neither structure could answer the other's question cheaply, which is why both are there.
## Why it is correct
The rule is a simulation, so the only thing to argue is that the two structures report the same thing a rescan would.
The pointer moves forward only, and it stops exactly where availability exceeds the current clock. Since the clock never goes backwards, a task pushed once stays a valid candidate forever afterwards, so nothing is pushed twice and nothing available is ever missed.
The heap orders by (duration, index), which is the rule verbatim. A pair, not
a bare duration: with bare durations two equally short tasks would come out in
whichever order the heap happened to hold them, and two correct programs would
disagree.
## The boundary that breaks a careless implementation
The jump must NOT push the task it jumps to and then fall through to a pop in
the same step without re-running the push loop. Setting time and continuing
is the clean shape, because the jump may make several tasks available at once,
not just the one that triggered it.
The availability test is <= time, not < time. A task appearing exactly when
the processor goes idle is available immediately.
The clock starts at 0, and with every t[i] >= 1 the first step is always a
jump. Starting the clock at t[0] of the unsorted input is a quiet bug that
only shows on inputs whose first task is not the earliest.
## Overflow
The clock is the value to watch: it reaches the last availability time plus the
total of every duration, which is 10^9 + 10^5 * 10^9, about 10^14. That is
far outside 32 bits, so hold the clock in 64 bits.
The comparison against availability is what breaks first if you do not: a wrapped clock goes negative, no task looks available, and the program either jumps repeatedly or stops early. Durations and availability times individually fit in 32 bits; only their running total does not.
## Related problems
Problem #189 runs tasks round-robin from a plain queue, where the next task is simply the one that has waited longest. Swapping that queue for a heap ordered by a stated key is the same move that turns the queue of #379 into the priority queue of #380, and it is worth seeing the same substitution in a scheduling setting rather than a graph one.
## Cost
Time O(n log n). Space O(n).
Constraints - `1 ≤ n ≤ 100000` - `1 ≤ t[i] ≤ 10^9` - `1 ≤ d[i] ≤ 10^9`
Input
The first line contains an integer n.
Each of the next n lines contains two integers: the availability time and the duration of one task, in index order starting from 0.
Output
Print the n task indices in the order they are run, separated by single spaces, on one line. Indices are 0-based.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.