Single-Threaded CPU
Medium · heap
A computer has a single processor that can run only one task at a time. You are given tasks, where tasks[i] = [enqueue, processing]: task i becomes available at time enqueue, and once started it needs exactly processing time units and cannot be interrupted.
The processor works like this:
- If it is idle and no task is available yet, it waits until the next task becomes available.
- If it is idle and some tasks are available, it starts the one with the shortest processing time. If several have the same processing time, it starts the one with the smallest index.
- When a task finishes, the processor is idle again at once, and it can start the next task at that same moment.
Return the indices of the tasks in the order the processor runs them.
Examples
Example 1
Input: tasks = [[1, 3], [2, 1], [2, 1], [10, 2]]
Output: [0, 1, 2, 3]
Task 0 runs from time 1 to 4. Tasks 1 and 2 are both waiting and need 1 unit each, so the smaller index goes first. Task 3 only arrives at time 10.
Example 2
Input: tasks = [[5, 2], [0, 6], [1, 1]]
Output: [1, 2, 0]
Only task 1 is available at time 0, and it runs until time 6. By then task 0 and task 2 are waiting, and task 2 is shorter.
Example 3
Input: tasks = [[3, 4]]
Output: [0]
Constraints
- 1 <= len(tasks) <= 10^5
- tasks[i] has exactly two numbers, enqueue and processing
- 0 <= enqueue <= 10^9
- 1 <= processing <= 10^4