Shortest-Job-First Process Scheduling
ByteDance● MediumNEW GRADPHONE SCREENProblem statement
One CPU runs a list of processes. Process i is processes[i] = [arrivali, bursti]: it arrives at time arrivali and needs bursti units of CPU time.
The CPU starts at time 0 and follows these rules:
- It runs one process at a time. Once a process starts, it runs to the end without being interrupted.
- Whenever the CPU is free at time
t, the waiting processes are those that have not run yet and havearrivali <= t. The CPU starts the waiting process with the smallestbursti. If several share that burst, it picks the one with the smallest index. - If no process is waiting, the CPU stays idle until the next process arrives.
Return the indices of the processes in the order the CPU runs them.
Function
scheduleProcesses(processes: int[][]) → int[]Examples
Example 1
processes = [[0,5],[1,3],[2,1],[3,7]]return = [0,2,1,3]At time 0 only process 0 has arrived, so it runs from 0 to 5. By time 5 processes 1, 2, and 3 are waiting with bursts 3, 1, and 7. Process 2 runs from 5 to 6, then process 1 from 6 to 9, then process 3 from 9 to 16.
Example 2
processes = [[4,2],[4,2],[0,3],[10,1]]return = [2,0,1,3]Process 2 runs from 0 to 3. Nothing is waiting at time 3, so the CPU is idle until time 4, when processes 0 and 1 arrive with the same burst 2. Process 0 has the smaller index, so it runs from 4 to 6, then process 1 from 6 to 8. The CPU is idle again until process 3 arrives at time 10.
Example 3
processes = [[6,4],[2,9],[3,1]]return = [1,2,0]Nothing has arrived at time 0, so the CPU waits until time 2 and runs process 1 from 2 to 11. Processes 0 and 2 arrive while it runs. Process 2 has the shorter burst, so it runs from 11 to 12, then process 0 from 12 to 16.
Constraints
1 <= processes.length <= 5000processes[i].length == 20 <= arrivali <= 10^91 <= bursti <= 10^5