Quick Overview

A coding question on non-preemptive CPU scheduling: processes arrive over time with fixed durations, and whenever the CPU is free it runs the shortest ready process, breaking ties by index. Return the execution order, handling idle gaps and simultaneous arrivals correctly and efficiently for large inputs.

Order Processes on One CPU by Shortest Ready Job

Company: ByteDance

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

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`.

Overview: A coding question on non-preemptive CPU scheduling: processes arrive over time with fixed durations, and whenever the CPU is free it runs the shortest ready process, breaking ties by index. Return the execution order, handling idle gaps and simultaneous arrivals correctly and efficiently for large inputs.

A single CPU runs a set of processes one at a time. You are given `processes`, where `processes[i] = [arrival, duration]`: process `i` becomes ready at time `arrival` and needs `duration` units 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, as a list of indices. ### Rules - 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` - `processes[i] = [arrival, duration]` - `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 for times in languages with fixed-width integers (`long` in Java, `long long` in C++). All values stay far below `2^53`. - `processes` is in no particular order. ### 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 = [[0, 4], [4, 1], [2, 3]] Output: [0, 1, 2] ``` Process `0` runs from `0` to `4`. At time `4`, process `2` (ready since time `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`.

Constraints

  • 0 <= len(processes) <= 10^5
  • processes[i] = [arrival, duration]
  • 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 for times in languages with fixed-width integers (long in Java, long long in C++). All values stay far below 2^53.
  • processes is in no particular order.

Examples

Input: ([],)

Expected Output: []

Explanation: No processes: the result is the empty list.

Input: ([[7, 3]],)

Expected Output: [0]

Explanation: Single process arriving at 7: the CPU idles from 0 to 7, then runs process 0.

Hints

  1. Decisions only happen when the CPU becomes free, or when it is idle and a process arrives, so you can move the clock from one such moment to the next instead of stepping one time unit at a time.
  2. At each decision moment you need the processes that have arrived by then and not started yet; looking at processes in arrival order tells you which ones join that group. A process arriving exactly at the decision moment counts.
  3. You repeatedly take the member of that group with the smallest duration, breaking ties by the smaller index, while new processes keep joining it; pick a representation that keeps both operations fast for 10^5 processes.

Loading coding console...

Show the approach

Approach

Simulate the CPU clock with a min-heap of ready processes keyed by (duration, index). Sort the indices by (arrival, index), keep a pointer j to the first process not yet moved into the heap, and keep the current time t (a 64-bit value) starting at 0.

Repeat until every process is scheduled: if the heap is empty and the next process in arrival order arrives after t, the CPU is idle, so jump t to that arrival. Then push every process with arrival <= t into the heap; using <= makes a process that arrives exactly when the CPU frees ready at that moment. Pop the minimum (duration, index), append its index to the answer and advance t by its duration. Nothing interrupts it: processes arriving meanwhile are only pushed at the next decision moment.

Invariant: at every decision moment t, the heap holds exactly the processes with arrival <= t that have not started. So the popped element is precisely the ready process with the smallest duration, ties broken by the smaller index, which is the rule. When the heap is empty some process is still unscheduled (pushed count equals scheduled count, which is below n), and jumping to the earliest remaining arrival is exactly the idle rule; after the jump at least one process is pushed, so the pop is always valid.

Edge cases: an empty list returns []; a single process returns [0] whatever its arrival; identical [arrival, duration] pairs come out in index order; times can reach about 10^14, so Java and C++ hold them in long / long long, and JavaScript numbers stay exact below 2^53.

Time complexity:
O(n log n)
Space complexity:
O(n)