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.

std::vector<std::pair<long long, long long>> schedule_tasks(
    const std::vector<std::pair<long long, long long>>& tasks);

Each task is an {arrival_time, duration} pair and each result entry is {task_index, completion_time}.

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^6\) tasks. The C++ performance case schedules ten times as many tasks.
• 0 <= arrival_time <= 10^9 and 1 <= duration <= 10^9.
• An empty task list returns an empty vector.
• 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.