Shortest Job First
Shortest Job First: given the burst times of processes all available at time zero, schedule them to minimise the average waiting time and return that average.
- 1 <= n <= 10⁵
- 1 <= burst[i] <= 10⁹
- All processes are available at time zero
Intuition
Shortest job first scheduling selects the waiting process with the smallest burst time whenever the CPU becomes free. The goal is minimising average waiting time, and SJF is provably optimal for that metric — no other non-preemptive algorithm does better.
The argument is an exchange: if a longer job runs before a shorter one, swapping them reduces the total waiting time, because the longer job's duration is then added to fewer processes' waits.
Two variants exist, and confusing them is the usual source of wrong answers:
- Non-preemptive SJF runs a chosen process to completion; preemptive SJF, also called Shortest Remaining Time First, interrupts the running process whenever a shorter job arrives.
Both need arrival times respected. Only processes that have already arrived are eligible, so the selection is over the arrived-and-waiting set, not over all processes.
When no process has arrived yet, the CPU idles until the next arrival. Skipping that idle period is a common bug — the clock must jump forward to the earliest arrival rather than scheduling something unavailable.
A min-heap keyed by burst time makes selection O(log n), with processes pushed as their arrival time is reached. Sorting alone is not enough, since eligibility changes over time.
Waiting time is completion − arrival − burst, and turnaround is completion − arrival. Getting these formulas backwards is easy and produces plausible-looking totals.
The practical objection to SJF is starvation: long processes may never run if short ones keep arriving. That is why real schedulers use aging or multi-level queues rather than pure SJF.
Running the shortest job first minimises average waiting time, because a job's duration delays every job queued behind it. Putting the cheapest delays first means the expensive one is paid by the fewest jobs — a classic exchange argument.
Approach
Before reading on: price up what the direct approach costs here, then ask why the locally best choice is safe to commit to and never revisit. Aim for O(n log n) time and O(1) space.
Understand why it is optimal
Running a shorter job first reduces total waiting time, since a long job's duration is then added to fewer processes' waits. This exchange argument proves optimality.
Distinguish the two variants
Non-preemptive runs to completion; preemptive (Shortest Remaining Time First) interrupts when a shorter job arrives. Confusing them is the usual source of wrong answers.
Select only from arrived processes
Eligibility depends on arrival time, so the choice is over processes already waiting — not over all processes in the input.
Idle when nothing has arrived
Advance the clock to the next arrival when no process is available. Scheduling an unarrived process is a common and silent error.
Use a min-heap on burst time
Push processes as their arrival time passes and pop the shortest. Sorting alone is insufficient, since eligibility changes as the clock advances.
Compute the metrics carefully
Waiting is completion − arrival − burst; turnaround is completion − arrival. Reversing these produces plausible but wrong averages.
Note the starvation problem
Long processes may never run if short ones keep arriving. Real schedulers add aging or multi-level queues rather than using pure SJF.
Cost of the simulation
Each process is pushed and popped once, giving O(n log n) time and O(n) space for the heap.
Solution & live demo
Common pitfalls
Adding the current job's own time to its wait
clock += t total += clock
total += clock clock += t
Waiting time is what elapses before a job starts, not including its own run. Advancing the clock first charges each job for its own duration and inflates every wait.
Sorting by arrival or leaving unsorted
# process in the given order
bt.sort()
The ordering is the entire algorithm — without it this is just first-come-first-served, which has a strictly worse average whenever a long job precedes a short one.
Returning the total instead of the average
return total
return total // len(bt)
The question asks for average waiting time. The unnormalised sum grows with the job count and isn't comparable across inputs.
Edge cases
It waits 0, so the average is 0.
Order does not matter; the average is the same for every permutation.
Most judges expect the floor of the average, so use integer division rather than a float.
Out of scope for this version — that variant needs a priority queue and preemption.