What is the pricing and subscription model for Hi👋SpeedAlgo?

The entire core curriculum of 12 patterns and 195 practice problems is 100% free to access with no credit card required. New accounts get 40 free coins once, the daily claim adds +20 coins once a day, and inviting a friend earns you +25 coins when they complete their first practice step. These are the only ways to earn coins. Each AI coach question costs 1-5 coins, priced by the server according to its size. AI coaching is free with your own Google Gemini, OpenAI or OpenRouter API key (BYOK). Coins also unlock extras for 24 hours: a Recall hint level (1 coin), a Solve solution reveal (2), a LeetCode problem card's solutions (1) and a pattern's extra canonical problems (1). Nothing on the site is sold for money: coins can only be earned, never bought.

What is the refund and cancellation policy?

Hi👋SpeedAlgo sells nothing for money: there are no subscriptions, renewals or charges, so there is nothing to cancel or refund. Nothing on the site is sold for money: coins can only be earned, never bought.

Who creates and maintains the curriculum?

Hi👋SpeedAlgo is developed and maintained by Hi👋WebEnterprise (https://hiwebenterprise.com), an engineering organization focused on developer education, deliberate practice methodologies, and cognitive ergonomics for technical interviews.

How does Hi👋SpeedAlgo prepare candidates for senior and staff SWE interviews?

Rather than rote LeetCode grinding, Hi👋SpeedAlgo uses deliberate practice for each pattern: learn the loop invariant, Big-O proof and edge cases from a side-by-side template and a step-by-step debugger, rebuild the template from memory, then solve a new problem on your own against a graded test suite.

11. Ready Heap: Single-Threaded CPU (LC 1834) • Invariant Proof & Speed-Run

Theory Context•Priority Queue / Heap

MediumLC 1834

Single-Threaded CPU (LeetCode 1834)

You will see how sorting by arrival, a min-heap of the arrived tasks and a clock that jumps over idle time simulate the CPU in O(N log N).

You get n tasks numbered 0 to n - 1 as a list tasks, where tasks[i] = [enqueueTime_i, processingTime_i]: task i can start from time enqueueTime_i on, and it needs processingTime_i units of time.

One CPU runs the tasks, one at a time, and each task runs to the end without a break. Whenever the CPU is free, it looks at the tasks that have already arrived and have not run yet, and picks the one with the shortest processing time; between equal times, the smaller index wins. If no task is waiting, the CPU stays idle until one arrives. A new task can start at the very moment the previous one ends.

Return the task indices in the order the CPU runs them.

Worked Examples

Example 1

Input:tasks = [[1,2],[2,4],[3,2],[4,1]]

Output:[0,2,3,1]

Explanation: At time 1 only task 0 has arrived, so it runs from 1 to 3. By then tasks 1 and 2 are waiting and task 2 is shorter, so it runs from 3 to 5. Task 3 arrived at 4 and needs 1 unit, so it beats task 1 and runs from 5 to 6; task 1 runs last, from 6 to 10.

Example 2

Input:tasks = [[7,10],[7,12],[7,5],[7,4],[7,2]]

Output:[4,3,2,0,1]

Explanation: All five tasks arrive at time 7, so the CPU runs them from shortest to longest: 2, 4, 5, 10 and then 12 units.

⚖️Formal Constraints & Bounds

1 <= tasks.length <= 10⁵
tasks[i] = [enqueueTime_i, processingTime_i]
1 <= enqueueTime_i, processingTime_i <= 10⁹

Deep-Dive & Conceptual Insights

Why It Works & Core Invariant

Sort by arrival and release every arrived task into a min-heap keyed (duration, index): its root is the CPU's next task, and when the heap is empty the clock jumps to the next arrival.

Real-World Scenario & Production Applications

A non-preemptive shortest-job-first scheduler is exactly this CPU: jobs arrive over time, and whenever the processor is free it runs the shortest job that is waiting, to completion. Discrete-event simulators advance their clock the same way, straight to the next event instead of ticking through idle time.

Subproblems & Recurrence Decomposition3 Phases

🧩Subproblem 1: Walk the Tasks in Arrival Order

Sort the task indices (not the tasks) by arrival once, and keep a pointer ptr to the first task not yet released. The original index survives, because it is both the tie-break and the answer.

Mathematical Recurrence / Code Invariant

order = sorted(range(len(tasks)), key=lambda i: tasks[i][0])
ptr = 0

Step-by-Step Execution Trace Table

Trace for Example 1, tasks = [[1,2],[2,4],[3,2],[4,1]]: order = [0, 1, 2, 3], time = 0, ptr = 0.

Turn	`time` at the start	Idle jump?	Released into `ready`	`ready` before the pop	Popped `(duration, i)`	`time` after	`result`
1	0	Yes: `ready` is empty and task 0 arrives at 1, so `time = 1`	task 0	`(2, 0)`	`(2, 0)`	3	`[0]`
2	3	No: task 1 already arrived at 2	tasks 1 and 2	`(2, 2)`, `(4, 1)`	`(2, 2)`	5	`[0, 2]`
3	5	No: `ready` is not empty	task 3	`(1, 3)`, `(4, 1)`	`(1, 3)`	6	`[0, 2, 3]`
4	6	No	none	`(4, 1)`	`(4, 1)`	10	`[0, 2, 3, 1]`

Scroll horizontally to see all columns, or expand to full screen

The trap mid-run: on tasks = [[10,5],[1,1],[10,1],[10,3]] task 1 runs from 1 to 2, and then ready is empty while the next arrival is at 10. The jump sets time = 10, the release loop puts tasks 0, 2 and 3 into ready together, and the CPU runs them shortest first: [1, 2, 3, 0].

Core Invariant Specification & Code Shape

Archetype Code Shape

Python

1	Only arrived tasks can run: sort the indices by arrival and release each task into a min-heap `ready` once `time` reaches its arrival.
2	`ready` holds exactly the tasks that have arrived by `time` and not run yet, keyed `(duration, i)`, so its root is the CPU's next task.
3	`order = sorted(...)`; `while len(result) < len(tasks)`: if `ready` is empty and the next arrival is later, jump `time` to it; release every task with arrival `<= time`; pop `(duration, i)`, add `duration` to `time`, append `i`; `return result`.
4	The trap: when `ready` is empty, jump `time` to `tasks[order[ptr]][0]`. Popping the empty heap crashes, and stepping `time` by 1 takes up to 10^9 steps.

Target: Single-Threaded CPU (LeetCode 1834). Sorting the indices, not the tasks, keeps each task's original index, which is both the tie-break and the answer. `ptr` walks this list once.

Boundary Model: Complete Binary Tree / Min-Max Heap Invariant

Heap maintains extreme element at root heap[0]. heappushpop maintains size bounded to K in O(log K) time.

Loop Invariant Termination

heapq.heappush(h, val); if len(h) > k: heapq.heappop(h) — peek min/max in O(1).

Conceptual Narrative

🧭 Conceptual Foundation & Pattern Intuition

Some problems are a clock ticking forward while items become available and one resource serves them. The resource may only choose among the items that have already arrived, and it wants the best of those. Ready Heap keeps exactly that set: sort the items by arrival once, and before each choice release every item whose arrival is at most the current time into a min-heap keyed by the choosing rule. For Single-Threaded CPU the rule is "shortest processing time, then smaller index", so the heap holds (duration, index) and its root is the next task to run.

🩺 The Analogy: One Doctor and a Waiting Room

Patients have appointment times and visits of different lengths. Whenever the doctor is free, she sees the waiting patient with the shortest visit, the lower ticket number first on a tie, and never interrupts a visit. If the waiting room is empty, she does not stand at the door checking every minute: she reads the appointment list and walks in at the next arrival time.

🪄 The Mathematical Harmony / Magic Trick

Code / Blueprint

order = sorted(range(len(tasks)), key=lambda i: tasks[i][0])
while len(result) < len(tasks):
    if not ready and time < tasks[order[ptr]][0]:
        time = tasks[order[ptr]][0]            # idle: jump to the next arrival
    while ptr < len(order) and tasks[order[ptr]][0] <= time:
        heapq.heappush(ready, (tasks[order[ptr]][1], order[ptr]))
        ptr += 1                              # release everything that has arrived
    duration, i = heapq.heappop(ready)        # shortest arrived task, smaller index on ties
    time += duration
    result.append(i)

time only moves forward, so ptr only moves forward: each task is pushed once and popped once. The heap always holds exactly the tasks that have arrived and not run, so its root is the task the CPU must pick.

💡 Summary

Sort by arrival, release into a heap keyed by the choosing rule, pop the best, and jump the clock when the heap is empty. One sort and one push and pop per task: $O(N \log N)$ time and $O(N)$ space.

No idle jump: when ready is empty the CPU has nothing to run, so heapq.heappop(ready) raises IndexError. Jump time to the next arrival, tasks[order[ptr]][0], before releasing; moving time forward by 1 instead takes up to 10^9 steps on [[1000000000, 1000000000]].
Releasing only one task per turn: after a jump several tasks can arrive at the same moment, and all of them must be in ready before the pick. On [[10,5],[1,1],[10,1],[10,3]] running task 0 as soon as the clock reaches 10 gives [1,0,2,3] instead of [1,2,3,0].
< instead of <= when releasing: a task that arrives exactly when the CPU frees up is available. On [[1,3],[4,1],[2,5]] task 1 arrives at 4, when task 0 ends, and must beat the longer task 2.
The wrong tie-break: equal durations go to the smaller index, not the earlier arrival. On [[3,2],[1,5],[2,2]] tasks 0 and 2 both take 2 units; task 0 wins even though task 2 arrived first.
Sorting tasks itself: it loses the original indices that the answer must return. Sort the indices by arrival instead.

Senior SWE Reasoning Architecture

4-Phase Thought Process Model

You will see how a senior engineer hears 'available at enqueueTime' and 'the shortest processing time' as a Ready Heap, and names the idle-CPU trap before it bites.

Pattern Recognition Signals

The 10-second spot

"Available to process at enqueueTime", "if the CPU is idle" and "the shortest processing time, then the smallest index": tasks become available over time, and at each free moment the CPU picks the best task among those already available. A clock plus a heap of the ready items: Ready Heap.

Formulating the Predicate & Invariants

Turning intuition into a boolean rule

Before each pop, ready holds exactly the tasks with arrival <= time that have not run, keyed (duration, i), so ready[0] is the next task. The rule: if ready is empty and the next arrival is later, jump time to it; release every task with arrival <= time; pop the root and add its duration to time.

Silent Failure Traps & Edge Cases

Where confident candidates still lose points

if not ready and time < tasks[order[ptr]][0]: time = tasks[order[ptr]][0]: the idle jump. Without it heapq.heappop(ready) pops an empty heap, and stepping time by 1 takes up to 10^9 steps on [[1000000000, 1000000000]].
while ptr < len(order) and tasks[order[ptr]][0] <= time: release with <= and in a loop, so a task that arrives as the CPU frees up counts, and every task that arrived together is in ready before the pick (Example 2 releases all five at time 7).
heapq.heappush(ready, (tasks[i][1], i)): the second key is the index, not the arrival time; on [[3,2],[1,5],[2,2]] task 0 beats task 2 although task 2 arrived first.
order = sorted(range(len(tasks)), key=lambda i: tasks[i][0]): sort the indices, not tasks itself, or the original index the answer needs is lost.

The 60-Second Interview Pitch

Say this out loud before you type a single line

I'd use a Ready Heap. The CPU can only choose among tasks that have already arrived, so I sort the task indices by arrival time once and keep a pointer into that list. Each turn I push every task whose arrival is at most the current time onto a min-heap keyed by processing time and then index, which is exactly the CPU's rule. I pop the root, add its duration to the time, and record its index. Time only moves forward, so the pointer only moves forward, and each task is pushed and popped once. The trap is the idle CPU: if the heap is empty, nothing has arrived yet, so I jump the time straight to the next arrival instead of popping an empty heap or ticking one unit at a time, which could take a billion steps. That's O(N log N) time and O(N) space.

So: spot items that arrive over time plus 'serve the best one available', release arrived tasks into a (duration, i) heap, jump the clock when it is empty, then pitch O(N log N).

Big-O Invariant Derivation

Complexity & Mathematical Proof

TIME COMPLEXITY

O(N log N)

Look at the code: order = sorted(range(len(tasks)), ...) costs O(N log N). The outer while len(result) < len(tasks) loop appends one index per turn, so it runs exactly N turns. In each turn the idle check and the jump are O(1), and heapq.heappop(ready) is O(log N). The inner release loop moves ptr forward and never back, so over the whole run it pushes each task exactly once: N pushes of O(log N) each. Total: O(N log N) + N · O(log N) + N · O(log N) = O(N log N). The idle jump is what makes the turn count N: ticking time by 1 would add a step for every idle unit, up to 10^9 of them.

SPACE COMPLEXITY

O(N)

order holds N indices and ready at most N tuples: O(N) extra. result is the output, N indices. There is no recursion.

Formal Recurrence Relation

T(N) = O(N log N) + N · O(log N) + N · O(log N) = O(N log N)

Derivation Progression

Sort by arrival

O(N log N)

order = sorted(range(len(tasks)), key=lambda i: tasks[i][0]).

Turns

N

Each turn appends one index to result, and the loop stops at len(tasks); the idle jump means no turn is spent waiting.

Releases

N × O(log N)

ptr only moves forward, so each task is pushed onto ready exactly once.

Picks

N × O(log N)

One heapq.heappop(ready) per turn on a heap of at most N tasks.

Total

O(N log N)

The sort and the heap work have the same order.

Variable Definitions

$N$

The number of tasks, len(tasks)

Memory Architecture & Bounds

🟣 Call Stack

O(1) Iterative, no recursion

🔵 Auxiliary Heap

O(N): order and ready

🟢 Output Space

O(N): result, one index per task

Boundary Best / Worst Cases

Best Case

$O(N \log N)$ : the sort runs whatever the arrival times

Average Case

$O(N \log N)$

Worst Case

$O(N \log N)$ : all N tasks arrive together and wait in ready

Binary Heap Priority Queue Tree

Synthesizing vector architecture diagram...

Staff+ Engineering Perspective

Senior SWE Deconstruction & Hardware Caveats

ARCHITECTURAL SIGNALS & INTERVIEW TRIGGERS

Triggers: "available to process at enqueueTime", "if the CPU is idle" and "the shortest processing time, then the smallest index". Items become available over time and each free moment serves the best one available so far: Ready Heap (sort by arrival, release into a heap, jump the clock when idle).

CONSTRAINTS & BOUNDS

$N \le 10^5$ tasks, arrival and processing times up to $10^9$ , so the clock can reach about $10^{14}$ (still exact in 64-bit integers and in Python). Rescanning every task at each pick is $O(N^2)$ ; the budget is $O(N \log N)$ time and $O(N)$ space.

FAANG PRODUCTION TRAPS & EDGE CASES

The idle CPU: with ready empty, a loop that advances time by 1 does up to $10^9$ useless steps per gap, and one that pops anyway crashes. In a long-running scheduler the same bug shows up as a busy-wait: the worker should sleep until the next arrival (or the next event), not poll every tick.

Core Algorithmic State Invariants

Only Arrived Tasks Compete

Before each pop, ready holds exactly the tasks with arrival <= time that have not run, keyed (duration, i), so its root is the CPU's rule applied to the right set.

Jump the Idle Clock

When ready is empty, nothing changes until the next arrival, so time = tasks[order[ptr]][0] skips the gap in one step instead of up to 10^9.

Forward Only

time never goes back, so ptr never goes back: each task is pushed once and popped once. One sort plus N pushes and N pops: O(N log N) time, O(N) space.

Theory Context•Priority Queue / Heap

MediumLC 1834

Single-Threaded CPU (LeetCode 1834)

You will see how sorting by arrival, a min-heap of the arrived tasks and a clock that jumps over idle time simulate the CPU in O(N log N).

Return the task indices in the order the CPU runs them.

Worked Examples

Example 1

Input:tasks = [[1,2],[2,4],[3,2],[4,1]]

Output:[0,2,3,1]

Example 2

Input:tasks = [[7,10],[7,12],[7,5],[7,4],[7,2]]

Output:[4,3,2,0,1]

Explanation: All five tasks arrive at time 7, so the CPU runs them from shortest to longest: 2, 4, 5, 10 and then 12 units.

⚖️Formal Constraints & Bounds

1 <= tasks.length <= 10⁵
tasks[i] = [enqueueTime_i, processingTime_i]
1 <= enqueueTime_i, processingTime_i <= 10⁹

Deep-Dive & Conceptual Insights

Why It Works & Core Invariant

Sort by arrival and release every arrived task into a min-heap keyed (duration, index): its root is the CPU's next task, and when the heap is empty the clock jumps to the next arrival.

Real-World Scenario & Production Applications

Subproblems & Recurrence Decomposition3 Phases

🧩Subproblem 1: Walk the Tasks in Arrival Order

Sort the task indices (not the tasks) by arrival once, and keep a pointer ptr to the first task not yet released. The original index survives, because it is both the tie-break and the answer.

Mathematical Recurrence / Code Invariant

order = sorted(range(len(tasks)), key=lambda i: tasks[i][0])
ptr = 0

Step-by-Step Execution Trace Table

Trace for Example 1, tasks = [[1,2],[2,4],[3,2],[4,1]]: order = [0, 1, 2, 3], time = 0, ptr = 0.

Turn	`time` at the start	Idle jump?	Released into `ready`	`ready` before the pop	Popped `(duration, i)`	`time` after	`result`
1	0	Yes: `ready` is empty and task 0 arrives at 1, so `time = 1`	task 0	`(2, 0)`	`(2, 0)`	3	`[0]`
2	3	No: task 1 already arrived at 2	tasks 1 and 2	`(2, 2)`, `(4, 1)`	`(2, 2)`	5	`[0, 2]`
3	5	No: `ready` is not empty	task 3	`(1, 3)`, `(4, 1)`	`(1, 3)`	6	`[0, 2, 3]`
4	6	No	none	`(4, 1)`	`(4, 1)`	10	`[0, 2, 3, 1]`

Scroll horizontally to see all columns, or expand to full screen

Core Invariant Specification & Code Shape

Archetype Code Shape

Python

1	Only arrived tasks can run: sort the indices by arrival and release each task into a min-heap `ready` once `time` reaches its arrival.
2	`ready` holds exactly the tasks that have arrived by `time` and not run yet, keyed `(duration, i)`, so its root is the CPU's next task.
3	`order = sorted(...)`; `while len(result) < len(tasks)`: if `ready` is empty and the next arrival is later, jump `time` to it; release every task with arrival `<= time`; pop `(duration, i)`, add `duration` to `time`, append `i`; `return result`.
4	The trap: when `ready` is empty, jump `time` to `tasks[order[ptr]][0]`. Popping the empty heap crashes, and stepping `time` by 1 takes up to 10^9 steps.

Target: Single-Threaded CPU (LeetCode 1834). Sorting the indices, not the tasks, keeps each task's original index, which is both the tie-break and the answer. `ptr` walks this list once.

Boundary Model: Complete Binary Tree / Min-Max Heap Invariant

Heap maintains extreme element at root heap[0]. heappushpop maintains size bounded to K in O(log K) time.

Loop Invariant Termination

heapq.heappush(h, val); if len(h) > k: heapq.heappop(h) — peek min/max in O(1).

Conceptual Narrative

🧭 Conceptual Foundation & Pattern Intuition

🩺 The Analogy: One Doctor and a Waiting Room

🪄 The Mathematical Harmony / Magic Trick

Code / Blueprint

order = sorted(range(len(tasks)), key=lambda i: tasks[i][0])
while len(result) < len(tasks):
    if not ready and time < tasks[order[ptr]][0]:
        time = tasks[order[ptr]][0]            # idle: jump to the next arrival
    while ptr < len(order) and tasks[order[ptr]][0] <= time:
        heapq.heappush(ready, (tasks[order[ptr]][1], order[ptr]))
        ptr += 1                              # release everything that has arrived
    duration, i = heapq.heappop(ready)        # shortest arrived task, smaller index on ties
    time += duration
    result.append(i)

💡 Summary

Sort by arrival, release into a heap keyed by the choosing rule, pop the best, and jump the clock when the heap is empty. One sort and one push and pop per task: $O(N \log N)$ time and $O(N)$ space.

No idle jump: when ready is empty the CPU has nothing to run, so heapq.heappop(ready) raises IndexError. Jump time to the next arrival, tasks[order[ptr]][0], before releasing; moving time forward by 1 instead takes up to 10^9 steps on [[1000000000, 1000000000]].
Releasing only one task per turn: after a jump several tasks can arrive at the same moment, and all of them must be in ready before the pick. On [[10,5],[1,1],[10,1],[10,3]] running task 0 as soon as the clock reaches 10 gives [1,0,2,3] instead of [1,2,3,0].
< instead of <= when releasing: a task that arrives exactly when the CPU frees up is available. On [[1,3],[4,1],[2,5]] task 1 arrives at 4, when task 0 ends, and must beat the longer task 2.
The wrong tie-break: equal durations go to the smaller index, not the earlier arrival. On [[3,2],[1,5],[2,2]] tasks 0 and 2 both take 2 units; task 0 wins even though task 2 arrived first.
Sorting tasks itself: it loses the original indices that the answer must return. Sort the indices by arrival instead.

Senior SWE Reasoning Architecture

4-Phase Thought Process Model

You will see how a senior engineer hears 'available at enqueueTime' and 'the shortest processing time' as a Ready Heap, and names the idle-CPU trap before it bites.

Pattern Recognition Signals

The 10-second spot

Formulating the Predicate & Invariants

Turning intuition into a boolean rule

Silent Failure Traps & Edge Cases

Where confident candidates still lose points

if not ready and time < tasks[order[ptr]][0]: time = tasks[order[ptr]][0]: the idle jump. Without it heapq.heappop(ready) pops an empty heap, and stepping time by 1 takes up to 10^9 steps on [[1000000000, 1000000000]].
while ptr < len(order) and tasks[order[ptr]][0] <= time: release with <= and in a loop, so a task that arrives as the CPU frees up counts, and every task that arrived together is in ready before the pick (Example 2 releases all five at time 7).
heapq.heappush(ready, (tasks[i][1], i)): the second key is the index, not the arrival time; on [[3,2],[1,5],[2,2]] task 0 beats task 2 although task 2 arrived first.
order = sorted(range(len(tasks)), key=lambda i: tasks[i][0]): sort the indices, not tasks itself, or the original index the answer needs is lost.

The 60-Second Interview Pitch

Say this out loud before you type a single line

I'd use a Ready Heap. The CPU can only choose among tasks that have already arrived, so I sort the task indices by arrival time once and keep a pointer into that list. Each turn I push every task whose arrival is at most the current time onto a min-heap keyed by processing time and then index, which is exactly the CPU's rule. I pop the root, add its duration to the time, and record its index. Time only moves forward, so the pointer only moves forward, and each task is pushed and popped once. The trap is the idle CPU: if the heap is empty, nothing has arrived yet, so I jump the time straight to the next arrival instead of popping an empty heap or ticking one unit at a time, which could take a billion steps. That's O(N log N) time and O(N) space.

So: spot items that arrive over time plus 'serve the best one available', release arrived tasks into a (duration, i) heap, jump the clock when it is empty, then pitch O(N log N).

Big-O Invariant Derivation

Complexity & Mathematical Proof

TIME COMPLEXITY

O(N log N)

SPACE COMPLEXITY

O(N)

order holds N indices and ready at most N tuples: O(N) extra. result is the output, N indices. There is no recursion.

Formal Recurrence Relation

T(N) = O(N log N) + N · O(log N) + N · O(log N) = O(N log N)

Derivation Progression

Sort by arrival

O(N log N)

order = sorted(range(len(tasks)), key=lambda i: tasks[i][0]).

Turns

N

Each turn appends one index to result, and the loop stops at len(tasks); the idle jump means no turn is spent waiting.

Releases

N × O(log N)

ptr only moves forward, so each task is pushed onto ready exactly once.

Picks

N × O(log N)

One heapq.heappop(ready) per turn on a heap of at most N tasks.

Total

O(N log N)

The sort and the heap work have the same order.

Variable Definitions

$N$

The number of tasks, len(tasks)

Memory Architecture & Bounds

🟣 Call Stack

O(1) Iterative, no recursion

🔵 Auxiliary Heap

O(N): order and ready

🟢 Output Space

O(N): result, one index per task

Boundary Best / Worst Cases

Best Case

$O(N \log N)$ : the sort runs whatever the arrival times

Average Case

$O(N \log N)$

Worst Case

$O(N \log N)$ : all N tasks arrive together and wait in ready

Binary Heap Priority Queue Tree

Synthesizing vector architecture diagram...

Staff+ Engineering Perspective

Senior SWE Deconstruction & Hardware Caveats

ARCHITECTURAL SIGNALS & INTERVIEW TRIGGERS

CONSTRAINTS & BOUNDS

FAANG PRODUCTION TRAPS & EDGE CASES

Core Algorithmic State Invariants

Only Arrived Tasks Compete

Before each pop, ready holds exactly the tasks with arrival <= time that have not run, keyed (duration, i), so its root is the CPU's rule applied to the right set.

Jump the Idle Clock

When ready is empty, nothing changes until the next arrival, so time = tasks[order[ptr]][0] skips the gap in one step instead of up to 10^9.

Forward Only

time never goes back, so ptr never goes back: each task is pushed once and popped once. One sort plus N pushes and N pops: O(N log N) time, O(N) space.

Rosetta Dual-Monaco Comparison

Python 3

CANONICAL INVARIANT TEMPLATE

CONCRETE: SINGLE-THREADED CPU (LEETCODE 1834)

T = O(N log N)S = O(N)

Pattern Implementation Mapping TableCanonical Invariant ⟷ Concrete Code ⟷ Engineering Rationale

Canonical Invariant	Concrete Code	Engineering Rationale
Sort the items by the moment they become available	`order = sorted(range(len(tasks)), key=lambda i: tasks[i][0])`	Sorting the indices, not the tasks, keeps each task's original index, which is both the tie-break and the answer. `ptr` walks this list once.
A heap of the items that are ready now, best on top	`ready: list[tuple[int, int]] = []`	`(duration, index)` tuples compare by duration first and index second, exactly the CPU's rule for picking a task.
Nothing is ready: jump the clock to the next release	`if not ready and time < tasks[order[ptr]][0]: time = tasks[order[ptr]][0]`	With an empty heap there is nothing to run, and nothing changes until the next task arrives. Jumping straight there skips the idle gap, which can be 10^9 time units long.
Release every item whose moment has come	`while ptr < len(order) and tasks[order[ptr]][0] <= time: i = order[ptr] heapq.heappush(ready, (tasks[i][1], i)) ptr += 1`	`<=` makes a task that arrives exactly as the CPU frees up available, and the `while` releases every task that arrived together before the pick.
Serve the best ready item and advance the clock	`duration, i = heapq.heappop(ready) time += duration result.append(i)`	The popped task runs to the end without a break, so the CPU is next free at `time + duration`.

Turn

time at the start

Idle jump?

Released into ready

ready before the pop

Popped (duration, i)

time after

result

Yes: ready is empty and task 0 arrives at 1, so time = 1

task 0

(2, 0)

[0]

No: task 1 already arrived at 2

tasks 1 and 2

(2, 2), (4, 1)

(2, 2)

[0, 2]

No: ready is not empty

task 3

(1, 3), (4, 1)

(1, 3)

[0, 2, 3]

none

(4, 1)

[0, 2, 3, 1]

order = sorted(range(len(tasks)), key=lambda i: tasks[i][0]) while len(result) < len(tasks): if not ready and time < tasks[order[ptr]][0]: time = tasks[order[ptr]][0] # idle: jump to the next arrival while ptr < len(order) and tasks[order[ptr]][0] <= time: heapq.heappush(ready, (tasks[order[ptr]][1], order[ptr])) ptr += 1 # release everything that has arrived duration, i = heapq.heappop(ready) # shortest arrived task, smaller index on ties time += duration result.append(i)

Turn

time at the start

Idle jump?

Released into ready

ready before the pop

Popped (duration, i)

time after

result

Yes: ready is empty and task 0 arrives at 1, so time = 1

task 0

(2, 0)

[0]

No: task 1 already arrived at 2

tasks 1 and 2

(2, 2), (4, 1)

(2, 2)

[0, 2]

No: ready is not empty

task 3

(1, 3), (4, 1)

(1, 3)

[0, 2, 3]

none

(4, 1)

[0, 2, 3, 1]

Canonical Invariant

Concrete Code

Engineering Rationale

Sort the items by the moment they become available

order = sorted(range(len(tasks)), key=lambda i: tasks[i][0])

Sorting the indices, not the tasks, keeps each task's original index, which is both the tie-break and the answer. `ptr` walks this list once.

A heap of the items that are ready now, best on top

ready: list[tuple[int, int]] = []

`(duration, index)` tuples compare by duration first and index second, exactly the CPU's rule for picking a task.

Nothing is ready: jump the clock to the next release

if not ready and time < tasks[order[ptr]][0]:
    time = tasks[order[ptr]][0]

With an empty heap there is nothing to run, and nothing changes until the next task arrives. Jumping straight there skips the idle gap, which can be 10^9 time units long.

Release every item whose moment has come

while ptr < len(order) and tasks[order[ptr]][0] <= time:
    i = order[ptr]
    heapq.heappush(ready, (tasks[i][1], i))
    ptr += 1

`<=` makes a task that arrives exactly as the CPU frees up available, and the `while` releases every task that arrived together before the pick.

Serve the best ready item and advance the clock

duration, i = heapq.heappop(ready)
time += duration
result.append(i)

The popped task runs to the end without a break, so the CPU is next free at `time + duration`.