Process Tasks on One CPU

Problem

A single-core worker receives tasks, where tasks[i] = [enqueueTime, processingTime]. Task i becomes available at enqueueTime. Whenever the worker is idle and tasks are available, it starts the available task with the shortest processing time, breaking ties by the smaller index, and runs it to completion without interruption. If nothing is available, it waits for the next task to arrive. Return the order in which the task indices are processed. There are up to 100,000 tasks, and times are up to 10^9.

Examples

Input:  tasks = [[1, 2], [2, 4], [3, 2], [4, 1]]
Output: [0, 2, 3, 1]
Why:    task 0 runs from 1 to 3; then 2 and 1 are waiting and 2 is shorter; at 5 task 3 is shortest

Input:  tasks = [[7, 10], [7, 12], [7, 5], [7, 4], [7, 2]]
Output: [4, 3, 2, 0, 1]
Why:    everything arrives together, so the order is simply shortest first

Input:  tasks = [[5, 3]]
Output: [0]
Why:    edge case, the worker waits until time 5 and runs the only task

Hints

0 / 3

1. Hint 1reveal
2. Hint 2locked
3. Hint 3locked

import heapq

def cpu_order(tasks):
    arrivals = sorted(range(len(tasks)), key=lambda i: tasks[i][0])
    ready, order, clock, k = [], [], 0, 0
    while len(order) < len(tasks):
        if not ready:
            clock = max(clock, tasks[arrivals[k]][0])        # skip idle time
        while k < len(arrivals) and tasks[arrivals[k]][0] <= clock:
            i = arrivals[k]
            heapq.heappush(ready, (tasks[i][1], i))          # shortest, then lowest index
            k += 1
        duration, i = heapq.heappop(ready)
        clock += duration
        order.append(i)
    return order

print(cpu_order([[1, 2], [2, 4], [3, 2], [4, 1]]))             # -> [0, 2, 3, 1]
print(cpu_order([[7, 10], [7, 12], [7, 5], [7, 4], [7, 2]]))   # -> [4, 3, 2, 0, 1]
print(cpu_order([[5, 3]]))                                     # -> [0]