Single-Threaded CPU

Single-Threaded CPU is LeetCode 1834, rated Medium. You are given a list of tasks where tasks[i] = [enqueueTime, processingTime]. A single-threaded CPU processes tasks one at a time. At any point when the CPU is idle, it looks at all available tasks (those whose enqueue time has passed) and picks the one with the shortest processing time. If there is a tie, it picks the task with the smaller original index. You need to return the order in which the CPU processes the tasks.

For example, with tasks = [[1,2],[2,4],[3,2],[4,1]], the CPU starts task 0 at time 1 and finishes at time 3. By then tasks 1 and 2 have arrived, and task 2 has the shorter processing time, so the CPU picks task 2 next. After task 2 finishes at time 5, task 3 has arrived and has a shorter processing time than task 1, so the CPU picks task 3. Finally it processes task 1. The result is [0, 2, 3, 1].

Why this problem matters

Simulation combined with a priority queue is one of the most common patterns in coding interviews. You will see it in job scheduling, event-driven systems, and operating system design questions. The core idea is always the same: process events in order, and when multiple events compete for a shared resource, use a heap to pick the best candidate efficiently.

This problem is a clean example of that pattern. There are no complex edge cases hiding behind the problem statement. The challenge is purely about organizing the simulation loop correctly and choosing the right data structure for selection.

The key insight

Sort the tasks by their enqueue time so you can process arrivals in order. Use a min-heap keyed by (processingTime, originalIndex) to always pick the shortest available task, breaking ties by index. The simulation loop has two phases: first, push all tasks that have arrived by the current time into the heap. Second, pop the best task from the heap and advance the clock by its processing time.

There is one important subtlety: if the heap is empty but tasks remain, the CPU is idle. In that case, jump the clock forward to the next task's enqueue time. Without this jump, you would loop forever waiting for tasks that have not arrived yet.

The solution

import heapq

def get_order(tasks: list[list[int]]) -> list[int]:
    indexed = sorted(enumerate(tasks), key=lambda x: x[1][0])
    heap = []
    result = []
    time = 0
    i = 0

    while i < len(indexed) or heap:
        if not heap and i < len(indexed) and indexed[i][1][0] > time:
            time = indexed[i][1][0]

        while i < len(indexed) and indexed[i][1][0] <= time:
            idx, (enqueue, process) = indexed[i]
            heapq.heappush(heap, (process, idx))
            i += 1

        process_time, idx = heapq.heappop(heap)
        time += process_time
        result.append(idx)

    return result

The first line pairs each task with its original index and sorts by enqueue time. This lets you walk through tasks in arrival order without losing track of which task is which. The time variable tracks the current CPU clock, and i tracks how far through the sorted task list you have scanned.

The outer loop runs until all tasks have been processed. If the heap is empty and the next task has not arrived yet, the CPU jumps forward to that task's enqueue time. Then you push all tasks whose enqueue time is at or before the current time into the heap. Finally, you pop the task with the smallest (processingTime, index) tuple, advance the clock, and record the result.

The key detail is that heapq in Python compares tuples element by element. By pushing (processingTime, originalIndex), ties on processing time are automatically broken by index, exactly as the problem requires.

Visual walkthrough

Here is a step-by-step trace with tasks = [[1,2],[2,4],[3,2],[4,1]]. Watch how the heap state changes as tasks arrive and the CPU picks the shortest one each time.

Notice how the CPU never sits idle in this example because new tasks keep arriving before the current one finishes. In cases where there is a gap, the time-jump logic ensures the simulation stays efficient.

Complexity analysis

Time. Sorting the tasks takes O(n log n). Each task is pushed into and popped from the heap exactly once, and each heap operation costs O(log n). The total across all tasks is O(n log n). The inner while loop that enqueues tasks runs at most n times total across all iterations of the outer loop, so it does not add to the complexity. The overall time is O(n log n).

Space. The sorted task list, the heap, and the result array each store at most n elements. Total space is O(n).

The building blocks

1. Event-driven simulation with a heap

The simulation pattern here is: maintain a clock, process events in order, and use a priority queue to decide what happens next. You will see this same structure in problems like meeting room scheduling, task scheduling with cooldowns, and network packet routing. The heap acts as the "decision maker" that picks the highest-priority event at each step.

2. Sort by arrival, process by priority

This two-phase approach, sort by one criterion and then use a heap keyed by another, appears whenever events arrive over time but are processed by a different priority. Sorting by arrival time lets you efficiently determine which events are available. The heap then handles the selection among available candidates. Separating "when does it become available" from "how important is it" is the core organizational principle.

Edge cases

• Single task. Only one task exists. The CPU processes it immediately. The result is [0].
• All tasks arrive at the same time. Every task is available from the start. The heap sorts them all by (processingTime, index) and they are processed in that order.
• Large gaps between arrivals. The CPU finishes all available tasks and goes idle. The time-jump logic skips forward to the next arrival rather than looping one time unit at a time.
• Tasks with the same processing time. Ties are broken by original index. The heap tuple (processingTime, index) handles this automatically since Python compares tuples left to right.
• Tasks arriving while CPU is busy. Tasks that arrive during processing accumulate in the heap and compete for the next slot when the CPU becomes free.

From understanding to recall

You have seen how sorting by enqueue time and using a min-heap keyed by processing time and index produces the correct execution order. The simulation loop is compact, but it combines several ideas: sorting, heap-based selection, and time management with idle-gap handling.

Remembering all of these pieces under interview pressure takes practice. Spaced repetition helps you internalize each building block separately, the sort-then-heap pattern, the time-jump for idle CPUs, the tuple comparison trick, so that they come together naturally when you encounter a new simulation problem. CodeBricks breaks this problem into those components and drills them at intervals tuned to your forgetting curve.

Related posts

• Task Scheduler - Another CPU scheduling problem with cooldown constraints
• Kth Largest Element in an Array - Heap fundamentals for priority-based selection
• Find K Pairs with Smallest Sums - Another problem combining sorting with heap-based selection

Heap-based simulation is a building block you will use again and again. CodeBricks helps you move from understanding the pattern to recalling it fluently, so the next time you see a scheduling problem, the approach clicks into place immediately.