Skip to main content

1834. Single-Threaded CPU

medium

Simulate a CPU scheduler that picks the shortest available task by enqueue time. A min-heap with tiebreaks — the kind of problem that sounds easy until you trip on the time-jump edge case.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

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 that the ith 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 will process the entire task without stopping. Return the order in which the CPU will process the tasks.

Constraints

  • tasks.length == n
  • 1 <= n <= 10^5
  • 1 <= enqueueTime_i, processingTime_i <= 10^9

Examples

Example 1

Input
tasks = [[1,2],[2,4],[3,2],[4,1]]
Output
[0,2,3,1]

Explanation: Walk forward in time: at t=1 task 0 enqueues, CPU picks it (the only option). Finishes at t=3. By then tasks 1 and 2 are available; both run-times are 4 and 2, pick task 2 (shorter). Continue picking shortest, breaking ties by index.

Example 2

Input
tasks = [[7,10],[7,12],[7,5],[7,4],[7,2]]
Output
[4,3,2,0,1]

Explanation: All tasks enqueue at t=7. Pick shortest first: task 4 (2), task 3 (4), task 2 (5), task 0 (10), task 1 (12).

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Two structures: tasks sorted by enqueue time (a queue), and a min-heap of currently-available tasks keyed by (processingTime, originalIndex).

Hint 2

Walk a time cursor t. Move every task with enqueueTime <= t into the heap.

Hint 3

If the heap is non-empty, pop and run that task. Advance t by its processing time and append its index to the result.

Hint 4

If the heap is empty, jump t forward to the next task's enqueueTime — don't waste time simulating idle ticks.

Solution approach

Reveal approach

Augment each task with its original index, then sort by enqueueTime. Maintain a min-heap of available tasks keyed by (processingTime, originalIndex) — Python's tuple ordering handles the tiebreak automatically. Walk a time cursor t and a sorted-tasks pointer i. Loop until both are exhausted: drain every task with enqueueTime <= t into the heap. If the heap is empty, jump t = tasks[i].enqueueTime (skip the idle gap — never simulate tick-by-tick on 10^9 timestamps). Otherwise pop the heap, append its index to the result, t += its processing time. O(n log n) overall, dominated by the sort and heap operations. The time-jump is the bug-magnet — without it you TLE on sparse enqueue times.

Complexity

Time
O(n log n)
Space
O(n)

Related patterns

  • heap
  • sorting
  • simulation

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Microsoft
  • Bloomberg

Practice these live with InterviewChamp.AI

Drill Single-Threaded CPU and Heaps problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →