Shortest Job First

A single processor runs jobs one at a time and never stops a job halfway. Job i is jobs[i] = (arrival, duration): it becomes available at time arrival and needs duration units of time.

Whenever the processor is free, it looks at the jobs that have arrived and have not run yet, and starts the one with the shortest duration. Ties go to the job that arrived earlier, and then to the smaller index. If no job is waiting, the processor sits idle until the next job arrives. A job that arrives at the exact moment the processor becomes free is already waiting.

Write run_order(jobs) that returns the list of job indices in the order the processor runs them.

Examples

run_order([(0, 3), (1, 9), (2, 6)])
# returns [0, 2, 1]

run_order([(5, 2), (0, 10), (5, 1)])
# returns [1, 2, 0]

run_order([(4, 1), (0, 2)])
# returns [1, 0]

In the first example job 0 runs from 0 to 3. At time 3 jobs 1 and 2 are both waiting, and job 2 is shorter. In the last example job 1 runs from 0 to 2, and the processor is idle until job 0 arrives at 4.

Constraints

• 0 <= len(jobs) <= 100,000, and the jobs are not given in arrival order
• 0 <= arrival <= 10^9 and 1 <= duration <= 10^9
• Thousands of jobs can be waiting at once, so scanning all of them every time the processor is free is too slow.