"""
p90 — Single-Threaded CPU (LC 1834)

INVARIANT: tasks sorted by enqueueTime, pointer ptr advances through them.
  Min-heap holds ready tasks as (proc_time, original_idx). When CPU idle and
  heap empty, fast-forward cur_time to next task's enqueue.
"""
from __future__ import annotations

import heapq
import random
from typing import List


def get_order(tasks: List[List[int]]) -> List[int]:
    """Sort + min-heap of (proc_time, idx) + fast-forward. O(n log n)."""
    n = len(tasks)
    # Attach original index BEFORE sorting.
    indexed = sorted(((enq, proc, i) for i, (enq, proc) in enumerate(tasks)),
                     key=lambda x: (x[0], x[2]))
    heap: List[tuple[int, int]] = []  # (proc_time, original_idx)
    order: List[int] = []
    cur_time = 0
    ptr = 0
    while ptr < n or heap:
        if not heap and ptr < n and indexed[ptr][0] > cur_time:
            # CPU idle; fast-forward.
            cur_time = indexed[ptr][0]
        # Push all newly-arrived tasks.
        while ptr < n and indexed[ptr][0] <= cur_time:
            _, proc, idx = indexed[ptr]
            heapq.heappush(heap, (proc, idx))
            ptr += 1
        # Run the shortest task.
        proc, idx = heapq.heappop(heap)
        order.append(idx)
        cur_time += proc
    return order


def get_order_brute(tasks: List[List[int]]) -> List[int]:
    """Oracle: naive O(n^2) simulation."""
    n = len(tasks)
    done = [False] * n
    order: List[int] = []
    cur_time = 0
    for _ in range(n):
        # Find ready tasks.
        ready = [i for i in range(n) if not done[i] and tasks[i][0] <= cur_time]
        if not ready:
            # Fast-forward to soonest pending.
            cur_time = min(tasks[i][0] for i in range(n) if not done[i])
            ready = [i for i in range(n) if not done[i] and tasks[i][0] <= cur_time]
        # Pick min (proc_time, idx).
        pick = min(ready, key=lambda i: (tasks[i][1], i))
        order.append(pick)
        done[pick] = True
        cur_time += tasks[pick][1]
    return order


def edge_cases() -> None:
    # LC example 1.
    assert get_order([[1, 2], [2, 4], [3, 2], [4, 1]]) == [0, 2, 3, 1]
    # LC example 2.
    assert get_order([[7, 10], [7, 12], [7, 5], [7, 4], [7, 2]]) == [4, 3, 2, 0, 1]

    # Single task.
    assert get_order([[1, 2]]) == [0]

    # All enqueue at 0 -> SJF, tie-break by idx.
    assert get_order([[0, 3], [0, 1], [0, 2]]) == [1, 2, 0]

    # Long gap requiring fast-forward.
    assert get_order([[1, 1], [100, 1]]) == [0, 1]


def stress_test() -> None:
    rng = random.Random(42)
    for _ in range(200):
        n = rng.randint(1, 6)
        tasks = [[rng.randint(0, 8), rng.randint(1, 8)] for _ in range(n)]
        g = get_order([t[:] for t in tasks])
        b = get_order_brute([t[:] for t in tasks])
        assert g == b, (tasks, g, b)


if __name__ == "__main__":
    edge_cases()
    stress_test()
    print("ALL TESTS PASSED")