Single-Threaded CPU
Understanding the Problem
This problem simulates a CPU scheduler. We have a set of tasks, each arriving at a specific time and taking a specific duration. The CPU is single-threaded, so it handles one task at a time. When it finishes a task (or starts idle), it picks the next task from all currently available tasks using a specific priority: shortest processing time first, and if there's a tie, the smaller original index wins.
The complication is that tasks arrive at different times. While the CPU is busy processing one task, new tasks may become available. A single sort by processing time is not enough, because availability depends on the current time, and the current time advances by different amounts depending on which task we picked. We have to track which tasks are available at each decision point, and those decision points shift as the CPU runs.
So at each moment the CPU finishes a task, we need the available task with the smallest processing time (and smallest index as a tiebreaker). A min-heap (priority queue) gives us that minimum in logarithmic time.
Key Constraints:
1 <= n <= 10^5-> With up to 100,000 tasks, O(n^2) would be 10^10 operations, which is too slow. We need O(n log n) or better.1 <= enqueueTime_i, processingTime_i <= 10^9-> Times can be very large. We can't iterate through every unit of time. We must jump between events.- Tasks arrive dynamically -> We need a data structure that supports efficient insertion and minimum extraction.
Approach 1: Brute Force Simulation
Intuition
Simulate the CPU's behavior step by step. At each decision point, when the CPU becomes idle, scan through all tasks to find which ones are available, then pick the one with the shortest processing time and smallest index among them.
Each time the CPU finishes a task, we look at every task, check whether its enqueue time has passed, skip any already-processed tasks, and pick the best candidate from the rest. If nothing is available yet, we fast-forward the clock to the next arrival rather than stepping through every unit of time.
Algorithm
- Track the current time and a boolean array to mark processed tasks.
- Repeat until all tasks are processed:
- Scan all tasks to find available ones (enqueue time <= current time and not yet processed).
- Among available tasks, pick the one with the smallest processing time (ties broken by index).
- If no tasks are available, jump the current time forward to the earliest unprocessed task's enqueue time.
- Add the chosen task to the result. Advance current time by its processing time.
- Return the result array.
Example Walkthrough
Code
- Time Complexity: O(n^2). For each of the n tasks, we scan all n tasks to find the best available one.
- Space Complexity: O(n). We use a boolean array of size n to track processed tasks, plus the result array.
The repeated full scan is what makes this quadratic. Sorting tasks by arrival time lets us add new arrivals with a single forward-moving pointer, and a min-heap keeps the shortest available task one operation away.
Approach 2: Sort + Min-Heap (Optimal)
Intuition
The brute force is slow at two things: finding available tasks and picking the best one. Two data structures fix both.
First, sort the tasks by enqueue time. Now arrivals can be consumed in order with a single pointer. Instead of scanning all tasks to check availability, we advance the pointer until every task that has arrived by the current time has been added.
Second, use a min-heap (priority queue) to hold the available tasks, ordered by (processing time, original index). Extracting the minimum gives the next task the CPU would pick.
The loop runs like this. When the CPU finishes a task, advance the current time, push any newly arrived tasks into the heap, then pop the top element. If the heap is empty but tasks remain, the CPU is idle, so jump the clock forward to the next arrival.
Two invariants hold every time we pop from the heap. First, every task with enqueue time <= currentTime is either in the heap or already processed, because the pointer pushes each arrival before we pop. Second, the heap orders by (processingTime, originalIndex), so its top is exactly the task the CPU rules select. Since currentTime only ever increases, a task that was unavailable at one pop can only become available later, never the reverse, so we never miss an eligible task. Together these guarantee the popped sequence matches the CPU's schedule.
Algorithm
- Create an array of (enqueueTime, processingTime, originalIndex) triples and sort it by enqueueTime.
- Initialize a min-heap ordered by (processingTime, originalIndex).
- Set
currentTime = 0and use pointeri = 0to track the next task to enqueue. - While the result is not complete:
- Push all tasks with enqueueTime <= currentTime into the heap.
- If the heap is empty, jump currentTime to the next task's enqueueTime, then push that task (and any others arriving at the same time).
- Pop the task with the smallest (processingTime, originalIndex) from the heap.
- Add its original index to the result. Advance currentTime by its processing time.
- Return the result.
Example Walkthrough
Code
- Time Complexity: O(n log n). Sorting takes O(n log n). Each task is pushed into and popped from the heap exactly once, and each heap operation is O(log n), giving O(n log n) total.
- Space Complexity: O(n). The sorted array stores n triples. The heap can hold up to n elements. The result array holds n elements.