Each task has an enqueue time and a processing time. A single-threaded CPU, whenever it is idle, starts the available task with the shortest processing time, breaking ties by smaller index. Return the order in which tasks are processed.
Before you code
Two orders are involved: tasks become available by enqueue time, and are chosen by (processing time, index). Sort by the first; keep a heap for the second.
Hints
- Sort task indexes by enqueue time.
- Keep a min-heap of
(processing_time, index)for tasks that have arrived. - When the heap is empty, jump the clock forward to the next arrival instead of ticking one unit at a time.
- After each task, push every task that has arrived by the new time.
Production & complexity notes
When solving Single-threaded CPU on LeetCode (medium), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Sift-up and sift-down to reinforce the underlying pattern.
What it practices
A priority queue with tie-breaking, from Sift-up and sift-down. Real operating system schedulers use the same idea with richer priorities.