1107. The Order the Processor Picks

One processor core runs n tasks. Task i becomes AVAILABLE at time enq[i] and then needs proc[i] units of uninterrupted work. The core follows this rule:

• when it is free and at least one task is available, it starts the available task with
• the SMALLEST processing time, breaking ties by the smaller index
• when it is free and nothing is available, it waits until the next task becomes
• available

Print the indices of the tasks in the order they are run, 0-based, separated by single spaces.

tasks (1,2) (2,4) (3,2) (4,1) -> 0 2 3 1 tasks (7,10) (7,12) (7,5) (7,4) (7,2) -> 4 3 2 0 1 tasks (0,3) (10,1) (20,1) -> 0 1 2

Trace the first line. At time 0 nothing is available, so the core waits until time 1 and starts task 0, finishing at 3. By then tasks 1 and 2 are available, taking 4 and 2 units, so it takes task 2 and finishes at 5. Now task 3 is available, taking 1 unit against task 1's 4, so task 3 runs and finishes at 6. Task 1 runs last.

## What most people try first

Sorting by availability and running in that order. That gives 0 1 2 3 on the first example instead of 0 2 3 1, because it never compares processing times.

Scanning all remaining tasks every time the core becomes free is correct and costs O(n^2). At n = 100000 that is 10^10 comparisons.

Sorting by processing time alone is wrong because a short task that is not yet available cannot be run.

## The method

Sort a copy of the tasks by availability. Sweep with a min-heap keyed by (processing time, index).

sort a copy by enq heap = empty clock = 0 i = 0 while some task is unfinished: push every task with enq <= clock, advancing i if the heap is empty: clock = enq of the next unpushed task continue pop the smallest (proc, index), output the index, clock = clock + proc

Each task enters and leaves the heap once, so the run is O(n log n).

## Why this is not an optimisation problem, and why it still needs an argument

The rule is given, so there is nothing to prove OPTIMAL here. What has to be argued is that the heap sweep produces the same sequence as the honest quadratic simulation, and that argument is the useful part.

At any moment the set of runnable tasks is exactly the set with enq <= clock that have not yet run. The clock only ever moves forward, so a task once pushed stays runnable for ever after, and the heap therefore holds precisely the runnable set at all times. Popping the minimum of that set is what the rule asks for.

The tie break has to live INSIDE the heap key, not outside it. Comparing on processing time alone leaves two equal tasks in an order decided by the heap's internal layout, which is not the index order the statement demands.

It is worth knowing WHY this rule is the one real processors reach for: shortest job first minimises the average completion time, which is exactly the exchange argument in problem #1102. Here the release times make that optimality claim false in general, which is problem #1143's subject.

## The boundary that breaks a careless implementation

When the heap empties and tasks remain, the clock must jump to the next availability time. Advancing it by one unit at a time is correct and can take 10^9 steps; leaving it alone loops for ever.

The push condition is enq <= clock, with <=. A task available exactly now is available.

Processing times of 0 are legal. The core runs such a task instantly and the clock does not move, so the loop must be driven by the number of tasks finished rather than by the clock changing.

## Sizes

n reaches 10^5 and both enq and proc reach 10^9, so the clock reaches about 10^14, far past the 2147483647 limit of a signed 32-bit integer. The clock must be 64-bit. No test here can demonstrate that, because the OUTPUT is a list of indices and a wrapped clock re-derives availability from scratch on the next step; the magnitude is stated so the declaration is right from the start rather than after a wrong answer.

## A related problem

Problem #1102 is this rule with every task available at time 0 and the output being the total waiting time instead of the order. That is the case where shortest-first is provably optimal, and this one is the case where it is simply the rule.

Constraints - `1 ≤ n ≤ 100000` - `0 ≤ enq ≤ 1000000000` - `0 ≤ proc ≤ 1000000000`