DSA problem
Single-Threaded CPU
You are given n tasks labeled from 0 to n - 1 represented by a 2D integer array tasks, where tasks[i] = [enqueueTime_i, processingTime_i] means the i-th task will be available to process at enqueueTime_i and will take processingTime_i to finish processing. You have a single-threaded CPU that can process at most one task at a time and will act in the following way:
If the CPU is idle and there are no available tasks to process, the CPU remains idle. If the CPU is idle and there are available tasks, the CPU will choose the one with the shortest processing time; if multiple tasks have the same shortest processing time, it will choose the task with the smallest index. Once a task is started, the CPU runs it to completion. A task can only be started by the CPU once its enqueue time has passed. Return the order in which the CPU will process the tasks.
The challenge is twofold: (1) tasks become available over time, so we cannot simply sort once and run a queue, and (2) the picking rule favours the shortest-processing task among those currently available, with ties broken by the original index. We need a priority queue that orders by (processingTime, originalIndex).
The optimal approach pairs sorting with a heap. First, attach the original index to each task and sort by enqueueTime — that gives us a "tasks ready by time t" cursor. Maintain a current simulation time and a min-heap of available tasks keyed by (processingTime, originalIndex). At each step, push every task whose enqueueTime is <= current time into the heap. If the heap is non-empty, pop and run the smallest task, advancing time by its processing time; otherwise jump time forward to the next task's enqueueTime. Each task enters and leaves the heap once, giving O(n log n) overall.
Examples
tasks = [[1,2],[2,4],[3,2],[4,1]][0,2,3,1]tasks = [[7,10],[7,12],[7,5],[7,4],[7,2]][4,3,2,0,1]tasks = [[1,1]][0]Constraints
- tasks.length == n
- 1 <= n <= 10^5
- 1 <= enqueueTime_i, processingTime_i <= 10^9
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.