Single-Threaded CPU
Problem Statement
You are given tasks, where tasks[i] = [enqueueTimei, processingTimei]. A single-threaded CPU can process one task at a time. When multiple tasks are available, it chooses the one with the shortest processing time, breaking ties by the smallest original index. Return the order of task indices processed by the CPU.
Input
An integer matrix tasks, where each row contains an enqueue time and a processing time. The original row position is the task index.
Output
An integer array containing the original indices in the order the CPU processes them.
Constraints
- •
1 <= tasks.length <= 10^5 - •
1 <= enqueueTimei, processingTimei <= 10^9
Examples
Example 1
tasks = [[1,2],[2,4],[3,2],[4,1]]
[0,2,3,1]Example 2
tasks = [[7,10],[7,12],[7,5],[7,4],[7,2]]
[4,3,2,0,1]Learning Objectives
- Sort jobs by enqueue time while preserving original indices for the answer.
- Use a min-heap of currently available tasks ordered by processing time and index.
- Advance the simulation clock correctly when the CPU is idle.
- Explain why unavailable future tasks must not enter the heap early.
Intuition
Pattern Recognition
The signal is available jobs, single CPU, shortest processing time, and original index tie-breaker. This is not a global sort by processing time, because a short task cannot be chosen before it arrives. The heap should contain only tasks whose enqueue time is less than or equal to the current clock.
Sort by enqueue time so future tasks can be revealed in order. Then a min-heap over available tasks chooses the next job by processing time, original index. If the heap is empty, the CPU has no work it can legally run, so jump the clock directly to the next enqueue time instead of incrementing one unit at a time.
Common mistakes
- ×Sorting only by processing time and accidentally running tasks before their enqueue time.
- ×Losing the original index after sorting the task array.
- ×Incrementing the clock one unit at a time through idle gaps, which is too slow for large times.
- ×Breaking ties by enqueue time instead of original index once tasks are available.
Algorithm Explanation
Key idea
Attach each task original index, then sort by enqueue time. Maintain a min-heap of tasks that have already arrived, ordered by processing time and then original index. The heap root is exactly the task the CPU must run next. A long clock value is safest because total processing time can exceed integer range.
Heap walkthrough
Use tasks = [[1,2],[2,4],[3,2],[4,1]]. Start at time 1 and add task 0, so the heap is [(2,0)] by (processing,index). Pop task 0, finish at time 3, and output [0]. Now tasks 1 and 2 have arrived; the heap is [(2,2),(4,1)], so pop task 2 and finish at time 5, output [0,2]. Add task 3, making the heap [(1,3),(4,1)]. Pop task 3, finish at time 6, then pop task 1 and finish at time 10. The final order is [0,2,3,1].
Algorithm
- Build an array of triples [enqueueTime, processingTime, originalIndex].
- Sort the triples by enqueue time.
- Keep a pointer to the next not-yet-added task and a clock value.
- If the heap is empty and the next task has not arrived, jump the clock to that task enqueue time.
- Push every task whose enqueue time is less than or equal to the clock into the min-heap.
- Poll the heap root, append its original index to the answer, and advance the clock by its processing time.
- Repeat until every task index has been output.
Solutions
Solution: Sorted enqueue scan with available-task heap
Use this for the canonical solution. It separates time eligibility from CPU priority, which is the core interview insight.
Sort tasks by enqueue time, but choose the next task from a min-heap of only currently available tasks. The heap comparator is processing time first, original index second.
Step-by-step
- Convert every task into [enqueueTime, processingTime, originalIndex].
- Sort the converted tasks by enqueue time.
- Maintain a pointer into the sorted array, a long clock, and a min-heap of available tasks.
- When the heap is empty, jump the clock to the next enqueue time.
- Add all tasks whose enqueue time is now reachable.
- Poll the shortest available task, append its original index, and add its processing time to the clock.
- Continue until the answer contains every index.
O(n log n)
O(n)
Sorting takes O(n log n), and each task is pushed and popped from the heap once. The heap can hold O(n) available tasks.
Java implementation
Dry Run
Sample input
tasks = [[1,2],[2,4],[3,2],[4,1]]. Heap entries are (processing,index) for tasks that have already arrived.
| clock | tasks added | heap before pop | chosen task | order |
|---|---|---|---|---|
| 1 | 0 | [(2,0)] | 0 | [0] |
| 3 | 1 and 2 | [(2,2),(4,1)] | 2 | [0,2] |
| 5 | 3 | [(1,3),(4,1)] | 3 | [0,2,3] |
| 6 | none | [(4,1)] | 1 | [0,2,3,1] |
The CPU never considers task 3 at time 3 because it has not arrived yet. Once it arrives by time 5, its short processing time makes it the next heap root.
Interview Tips
Separate the two orders out loud: sort by enqueue time to reveal tasks, then heap by processing time and original index to choose among available tasks. Use a long clock and jump idle gaps directly. The original index must travel with the task from the moment you sort.
Likely follow-ups
- How would the result change if ties used enqueue time before original index?
- How would you support multiple identical CPUs?
- How would you compute average waiting time in addition to order?
- What if tasks could be preempted when a shorter task arrives?
Similar Problems
Key Takeaways
- The heap contains only tasks that have already arrived.
- CPU priority is **processing time**, then **original index**.
- Jump the clock over idle gaps instead of simulating every time unit.
- Preserve original indices before sorting so the answer can be emitted correctly.