Single-Threaded CPU
Medium · Heap & Counting · Array · Sorting · Heap (Priority Queue)
Problem
You are given n tasks labelled 0 to n - 1 as a list tasks, where tasks[i] = [enqueueTime, processingTime]: task i becomes available at enqueueTime and takes processingTime units to run.
A single-threaded CPU processes them like this:
- If the CPU is idle and no tasks are available, it stays idle.
- If the CPU is idle and tasks are available, it starts the one with the shortest processing time, breaking ties by the smallest index.
- A started task runs to completion without interruption, and the CPU can start another task at the very moment it finishes.
Return the order in which the CPU processes the tasks.
Examples
Input: tasks = [[1,5],[2,3],[3,1],[4,1]] Output: [0,2,3,1]
Task 0 runs from 1 to 6; by then tasks 1 to 3 are waiting, and the two 1-unit tasks go first, by index.
Input: tasks = [[5,2],[5,2],[5,1]] Output: [2,0,1]
All arrive at 5: task 2 is shortest, then tasks 0 and 1 tie and go by index.
Input: tasks = [[1,2],[8,4],[2,3]] Output: [0,2,1]
Task 0 runs 1 to 3, task 2 runs 3 to 6, then the CPU idles until task 1 arrives at 8.
Constraints
- 1 <= len(tasks) <= 10^5
- 1 <= enqueueTime, processingTime <= 10^9
Approaches
- Baseline: scan every remaining task at each step — time O(n²), space O(n)
Follow-up
The same simulation answers other questions about the schedule, such as how long tasks wait in total, and extends to several processors with a second heap of finishing times. See the use cases.
Related problems
Start free on Cariara · Coding problems · System design studio
