AAlgoLoopSpaced repetition for LeetCode
MEDIUMHeap / Priority QueueLeetCode ↗

Single-Threaded CPU

The key idea

Whenever the CPU is free, the next task to run is the available task with the smallest processing time (ties broken by index). A min-heap keyed on (processingTime, index) gives that pick in O(log n); sort the tasks by enqueue time so you only add tasks that have actually arrived.

Problem

You are given n tasks labeled 0 to n - 1 as a 2-D array tasks, where tasks[i] = [enqueueTime[i], processingTime[i]]. Each task i becomes available at time enqueueTime[i] and needs processingTime[i] units of work to finish.

The CPU has a single thread that runs the tasks one at a time using these rules:

- If the CPU is idle and no task is available, it stays idle.
- If the CPU is idle and there are available tasks, it picks the one with the shortest processingTime. Ties are broken by the smallest index.
- Once a task starts, it runs to completion without interruption.
- The moment a task finishes, the CPU can instantly start the next one.

Return the order in which the CPU processes the tasks, as a list of their indices.

Constraints

Examples

Input: tasks = [[1,2],[2,4],[3,2],[4,1]] Output: [0,2,3,1]
Input: tasks = [[7,10],[7,12],[7,5],[7,4],[7,2]] Output: [4,3,2,0,1]

Complexity

Time: O(n log n) Space: O(n)

See the full solution

410310
Step-by-step visualization
Start free →

More Heap / Priority Queue problems