Single-Threaded CPU

MediumHeapheap

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

A CPU runs one task at a time. You are given tasks, where tasks[i] = [enqueueTime, processingTime] means task i becomes available at time enqueueTime and needs processingTime units to finish once started. The CPU follows these rules, starting at time 0: - If it is idle and no task is available, it waits until the next task becomes available. - If it is idle and tasks are available, it starts the one with the **shortest processingTime**; ties go to the **smallest index**. - A started task runs to completion without interruption. The CPU may pick its next task the instant the previous one ends, and tasks whose enqueueTime equals that instant count as available. Return the task indices in the order the CPU processes them. Target O(n log n).

Examples

Input: tasks = [[2,4],[3,3],[3,1],[5,2]]
Output: [0,2,3,1]
The CPU waits until 2 and runs task 0 until 6. Tasks 1, 2 and 3 are all waiting then. Task 2 (1 unit) runs until 7, task 3 (2 units) until 9, and task 1 last.
Input: tasks = [[5,2],[5,2],[5,1],[20,1]]
Output: [2,0,1,3]
At 5, task 2 is shortest. Tasks 0 and 1 tie on length, so task 0 goes first. The CPU is then idle until task 3 arrives at 20.

Constraints

  • 1 <= tasks.length <= 10^5
  • 1 <= enqueueTime, processingTime <= 10^9

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More heap problems