646. Single-Threaded CPU
You are given n tasks numbered 0 to n − 1, described by two integer arrays of equal length: enqueueTime[i] is the moment task i becomes available, and processingTime[i] is how long it needs to run.
A single-threaded CPU works through them under three rules:
- it runs one task at a time and never interrupts a task mid-run;
- whenever it goes idle and at least one available task is waiting, it starts the waiting task with the shortest processing time, breaking ties by the lowest index;
- if it goes idle and nothing has arrived yet, it sleeps until the next enqueue time.
Return the task indices in the order the CPU executes them.
Example 1:
Input: enqueueTime = [1, 2, 3, 4], processingTime = [2, 4, 2, 1]
Output: [0, 2, 3, 1]
Explanation: At t = 1 only task 0 exists, so it runs until t = 3. Then tasks 1 (time 4) and 2 (time 2) are waiting — task 2 is shorter and runs until t = 5. Then tasks 1 and 3 are waiting — task 3 (time 1) wins, then task 1 finishes last.
Example 2:
Input: enqueueTime = [7, 7, 7, 7, 7], processingTime = [10, 12, 5, 4, 2]
Output: [4, 3, 2, 0, 1]
Explanation: All five tasks arrive together at t = 7, so the CPU simply drains them shortest-first: 2, 4, 5, 10, 12.
Constraints:
- 1 ≤ n ≤ 10⁵
- 1 ≤ enqueueTime[i], processingTime[i] ≤ 10⁹
Hints:
Simulate a clock. Whenever the CPU is idle you need exactly two things: which tasks have arrived by now, and which of those minimizes (processingTime, index). If nothing has arrived, jump the clock straight to the next enqueue time — never tick one unit at a time.
Sort the task indices by enqueue time, and push them into a min-heap keyed by (processingTime, index) as the clock passes their arrival. Each idle moment then pops the heap in O(log n). Keep the clock in a 64-bit integer — the total running time can exceed 2^31.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: enqueueTime = [1, 2, 3, 4], processingTime = [2, 4, 2, 1]
Expected output: [0, 2, 3, 1]