Single-Threaded CPU - Video Solutions

Problem Overview: You are given tasks where each task has an enqueueTime and processingTime. A single-threaded CPU can process only one task at a time and always picks the available task with the smallest processing time (breaking ties by index). The goal is to return the order in which the CPU processes the tasks.

Approach 1: Sort + Priority Queue Simulation (O(n log n) time, O(n) space)

This is the standard scheduling simulation used in most accepted solutions. First attach each task's original index and sort tasks by enqueueTime using sorting. Iterate through time while pushing all tasks whose enqueue time is less than or equal to the current time into a min-heap. The heap is ordered by (processingTime, index) so the CPU always selects the shortest job first with deterministic tie-breaking.

At each step, pop the top task from the heap (priority queue), append its index to the result, and advance the current time by its processing time. If the heap becomes empty but tasks remain, jump the current time to the next task's enqueue time. This approach efficiently models the scheduler and guarantees that every push/pop operation costs O(log n), giving an overall O(n log n) time complexity with O(n) extra space.

Approach 2: Multimap / TreeMap Scheduling (O(n log n) time, O(n) space)

Instead of explicitly sorting the array, store tasks in a structure ordered by enqueue time such as a multimap or TreeMap. This structure keeps tasks automatically sorted as they are inserted. Maintain another ordered structure (typically a min-heap) for currently available tasks prioritized by processing time and index.

Simulate the CPU clock the same way as the heap approach: move tasks from the time-ordered map into the processing heap whenever their enqueue time becomes available. Extract the shortest task, process it, and update the clock. Using a balanced tree avoids the explicit sort step but still performs ordered insertions and lookups in O(log n). Total complexity remains O(n log n) time with O(n) space.

The key idea behind both solutions is separating two concerns: ordering tasks by arrival time and selecting the best available task to run. Arrival ordering is handled by sorting or a tree structure over the array, while task selection is handled by a priority queue.

Recommended for interviews: The sort + priority queue approach. Interviewers expect you to recognize this as a scheduling simulation similar to Shortest Job First (SJF). A brute simulation without a heap becomes inefficient, while the heap-based scheduler demonstrates strong understanding of priority queues and event-driven simulation.