← DSA Atlas
Dedicated problem page · #1834

Single-Threaded CPU

MediumHeap and Priority QueueEvent simulation with a min-heap of available jobsMin-heap (priority queue) plus a sorted enqueue pointer
Solve on LeetCode ↗
1834
MediumHeap and Priority QueueMin-heap (priority queue) plus a sorted enqueue pointerEvent simulation with a min-heap of available jobs

Single-Threaded CPU

You have a single-threaded CPU and n tasks, where tasks[i] = [enqueueTime_i, processingTime_i]. A task becomes available at its enqueue time. When the CPU is free it must, from the tasks that have already become available, pick the one with the smallest processing time (breaking ties by the smaller task index), run it to completion without interruption, then immediately become free again. If no task is available the CPU idles until the next one arrives. Return the order in which the tasks are processed, as a list of their original indices.

Open official problem prompt ↗
In plain English

Reproduce the exact execution order of a greedy single-threaded scheduler: whenever the CPU is free, it runs the shortest available task (smallest index on ties), and we report which task index runs at each step.

Picture it like this

Think of a single doctor in a walk-in clinic. Patients arrive at different times and sit in the waiting room. When the doctor finishes with someone, they don't take whoever arrived first — they take the patient whose visit will be quickest (and if two would take equally long, the one with the lower ticket number). If the room is empty, the doctor waits for the next arrival.

Example
Input
tasks = [[1,2],[2,4],[3,2],[4,1]]
Output
[0, 2, 3, 1]
Why
Task 0 arrives at t=1 and runs t=1..3; by t=3 tasks 1 and 2 are available, task 2 has the smaller processing time (2<4) so it runs t=3..5; then task 3 (proc 1) beats task 1 (proc 4) and runs t=5..6; finally task 1 runs.
Constraints
tasks.length == n1 <= n <= 10^51 <= enqueueTime_i, processingTime_i <= 10^9
Pattern lesson

See the pattern, then code

Event simulation with a min-heap of available jobs
Recognition clue

Jobs arrive over time and, whenever the server frees up, you must repeatedly pick the 'best' currently-available job by some key (shortest processing, smallest index). Arrival order differs from execution order — that gap between 'available' and 'chosen' is the signal for a heap-driven simulation.

↗
Heap and Priority Queue

Top k, kth value, repeated minimum extraction, scheduling, or merging sorted streams.. Sort tasks by enqueue time so you can reveal them in arrival order with a single forward pointer, but choose among the revealed ones with a min-heap keyed on (processingTime, originalIndex). The heap always surfaces the correct next task in O(log n), and the tie-break falls out of the tuple ordering.

New words, made simpleKnow these before the algorithm
Enqueue time
The moment a task becomes eligible to be picked; before it, the task simply does not exist to the scheduler.
Processing time
How long a task occupies the CPU once started; it runs to completion without preemption.
Min-heap
A priority queue that returns its smallest element in O(1) and pops/pushes in O(log n); here keyed on the tuple (processingTime, index).
Non-preemptive
Once a task starts it cannot be paused or swapped out, so the clock jumps forward by the full processing time.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Re-scan all tasks each time the CPU frees up

With n up to 10^5 the quadratic scan is roughly 10^10 operations and times out.

Keep a done[] array; each time the CPU is free, linearly scan every task to find the available, unfinished one with the smallest (proc, index).

Time O(n^2)Space O(n)
Best choiceSort by enqueue time + min-heap of available tasks

Each task is pushed and popped once, so total heap work is n log n — fast enough and directly models the rules.

Reveal tasks in arrival order with one pointer, keep the currently-available ones in a (proc, index) min-heap, and pop the best each time the CPU frees; jump the clock to the next arrival when the heap empties.

Time O(n log n)Space O(n)
The rule we keep true

Invariant

At every moment the clock reaches, the heap contains exactly the tasks that have already been enqueued but not yet processed, ordered so its top is the next task the CPU must run.

Why this is correct

Reasoning

The scheduler's choice depends only on the set of tasks available at the instant the CPU is free — and the clock only advances when a task finishes or when we deliberately jump it to the next arrival. Because tasks are admitted in nondecreasing enqueue order via the pointer, whenever we pop, every task with enqueue <= clock is already in the heap, so the (proc, index) minimum we pop is provably the exact task the rules require.

The algorithm in three movesSay these aloud before coding
1Sort task indices by enqueue time so tasks can be admitted in arrival order

t=1: heap={(2,0)} -> run 0, t->3

2Advance a clock; push every task whose enqueue time <= clock into a (proc, index) min-heap

t=3: heap={(2,2),(4,1)} -> run 2, t->5

3If the heap is empty but tasks remain, jump the clock forward to the next task's enqueue time

t=5: heap={(1,3),(4,1)} -> run 3, t->6 -> run 1

4Pop the smallest (proc, index) task, append its index to the answer, and advance the clock by its processing time

5Repeat until all n tasks have been output

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
[1,2]0
[2,4]1
[3,2]2
[4,1]3
1 · Readsorted arrivals: idx0@1, idx1@2, idx2@3, idx3@4
2 · AskWhat is available at the earliest arrival?
3 · Update statetime=1, heap={(2,0)}
4 · ResultOnly task 0 is available; pop it, append 0, time -> 1+2 = 3.
Key takeaway

Tasks shown as [enqueue,proc]; at t=3 both task 1 and task 2 are available, and the heap picks task 2 for its smaller processing time.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 6-7Order tasks by arrival

    Sorting the indices (not the tasks) by enqueue time lets a single forward pointer reveal tasks in the order they become available while preserving each task's original index for the output.

  2. 2
    Lines 12-15Admit all currently-available tasks

    The inner while pushes every task whose enqueue time has passed into the heap as (processingTime, index), so the heap holds exactly the eligible candidates.

  3. 3
    Lines 16-18Handle the idle CPU

    If nothing is available yet but tasks remain, fast-forward the clock to the next arrival instead of ticking one unit at a time.

  4. 4
    Lines 19-22Run the best task

    Popping the heap gives the smallest processing time with the smallest index on ties; append its index and advance the clock by its full processing time (non-preemptive).

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • A gap where the CPU goes idle because all remaining tasks enqueue later than the current clock
  • Several tasks sharing the same enqueue time — resolved purely by (proc, index) ordering
  • Tasks with equal processing times — the smaller original index must win via the tuple's second field
  • A single task (n = 1) returns immediately
  • Large timestamps up to 10^9 — use the clock jump rather than incrementing time unit by unit
!

Common beginner mistakes

  • Comparing on processing time alone and forgetting the index tie-break, which corrupts order among equal-length tasks
  • Sorting the tasks in place and losing the original indices needed for the answer
  • Advancing the clock by 1 each step instead of jumping to the next enqueue time, causing timeouts with 10^9 gaps
  • Only admitting one task per CPU-free step instead of draining every task with enqueue <= clock
  • Using the raw enqueue time as the heap key — the scheduler picks by processing time, not arrival time
Check your understanding

At t=3 tasks 1 and 2 are both available with processing times 4 and 2. If task 2 instead had processing time 4 as well, which would the CPU pick and why?

More in Heap and Priority Queue

#215Kth Largest Element in an ArrayBounded min-heap of size k#295Find Median from Data StreamTwo balanced heaps#373Find K Pairs with Smallest Sumsk-way merge with a heap#502IPOGreedy with a max-heap of affordable options#621Task SchedulerFill idle slots around the most frequent task#692Top K Frequent WordsCount then heap-order by frequency and word