Order Processes on One CPU by Shortest Ready Job

A single CPU runs a set of processes one at a time. Process `i` becomes ready at its arrival time and needs a fixed amount of CPU time. Once started, a process runs to completion without interruption. Whenever the CPU is free, it starts the ready process with the shortest duration. Return the order in which the processes run. The report names only the topic of this round, process scheduling; the rules below fix one standard non-preemptive policy so that the answer is unique. ### Function Signature ```python def schedule_order(processes: list[list[int]]) -> list[int]: ``` ### Rules - `processes[i] = [arrival, duration]`. The result lists every index from `0` to `len(processes) - 1` exactly once, in the order the processes start. - The CPU is free at time `0`. A process is ready at time `t` when `arrival <= t` and it has not started yet; a process that arrives at exactly the moment the CPU becomes free is ready at that moment. - Whenever the CPU is free and at least one process is ready, it immediately starts the ready process with the smallest `duration`. Ties go to the smaller index. - If the CPU is free and no process is ready, it stays idle until the next arrival. - A process started at time `s` finishes at `s + duration`, and the CPU is free again at that time. - Return `[]` when there are no processes. ### Constraints - `0 <= len(processes) <= 10^5` - `0 <= arrival <= 10^9` - `1 <= duration <= 10^9` - Every input value fits in a 32-bit signed integer, but start and finish times can exceed `2^31 - 1` (up to about `10^14`), so use 64-bit integers in languages with fixed-width integers. All values stay far below `2^53`. - `processes` is in no particular order. ### Examples **Example 1** ```text Input: processes = [[0, 5], [1, 3], [2, 1], [3, 3]] Output: [0, 2, 1, 3] ``` At time `0` only process `0` is ready, so it runs from `0` to `5`. At time `5`, processes `1`, `2` and `3` are ready; process `2` is the shortest and runs from `5` to `6`. Processes `1` and `3` both need `3` units, so the smaller index, `1`, runs from `6` to `9`, then process `3` from `9` to `12`. **Example 2** ```text Input: processes = [[10, 2], [0, 3], [10, 1]] Output: [1, 2, 0] ``` Process `1` runs from `0` to `3`. Nothing is ready between `3` and `10`, so the CPU idles. At time `10`, processes `0` and `2` are both ready; process `2` is shorter and runs from `10` to `11`, then process `0` from `11` to `13`. **Example 3** ```text Input: processes = [[0, 4], [4, 1], [2, 3]] Output: [0, 1, 2] ``` Process `0` runs from `0` to `4`. At time `4`, process `2` (ready since `2`) and process `1` (arriving exactly at `4`) are both ready; process `1` is shorter and runs from `4` to `5`, then process `2` from `5` to `8`.