Single-CPU Task Scheduler

Implement schedule_tasks(tasks), which simulates a node that runs jobs on a single core and returns the order in which they complete.

A research cluster node runs backtest jobs on a single pinned core. Jobs are submitted over the day, each with a known runtime, and the node runs one job at a time to completion (no preemption). When the core frees up, it picks the shortest job among those already submitted; if nothing has been submitted yet, it sits idle until the next submission.

You are given tasks, a sequence of (arrival_time, duration) integer pairs; the position of a task in the sequence is its index. The scheduler works like this:

• When the CPU is free at time \(t\), it chooses among tasks with arrival_time <= t the one with the smallest duration, breaking ties by earliest arrival_time, then by smallest input index.
• If no task has arrived, the CPU jumps forward to the next arrival.
• The chosen task runs for exactly duration and completes; the CPU is free again at its completion time.

Return the (task_index, completion_time) pairs in the order the tasks complete.

def schedule_tasks(tasks: list[tuple[int, int]]) -> list[tuple[int, int]]: ...

Examples

schedule_tasks([(0, 3), (1, 9), (2, 3)])
# [(0, 3), (2, 6), (1, 15)]  (at t=3 both remaining jobs have arrived; the 3-long one wins)

schedule_tasks([(5, 2), (0, 4)])
# [(1, 4), (0, 7)]  (idle from t=4 to t=5 waiting for task 0)

Constraints

• Up to \(10^5\) tasks.
• 0 <= arrival_time <= 10^9 and 1 <= duration <= 10^9.
• An empty task list returns [].
• Rescanning every waiting task at each pick is quadratic and will not finish in time on the largest hidden test; keep the ready set in a structure that hands you the minimum cheaply.