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.
Open on GeeksforGeeks ↗Intuition
It is tempting to think the order barely matters since every job runs either way. It matters enormously: a job of length L scheduled early charges its full L to the waiting time of every job behind it. That multiplier is the whole problem. Put the shortest first so the big multipliers land on the small numbers, then sweep with a running clock.
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
Identify the real cost
A job's waiting time is the sum of the burst times of everything scheduled before it. So a job of length L placed at position k contributes L to the waiting time of each of the n - k jobs behind it. Long jobs early are expensive precisely because that multiplier is large.
Prove the greedy with an exchange argument
Suppose an optimal schedule runs job A immediately before job B with A longer. Swapping them lowers B's wait by A - B and raises A's by the same amount, but every other job is unaffected — and since more jobs sit behind the pair than in front, the total never increases. Repeating the swap sorts the list, so sorted order is optimal.
Sweep with a running clock
After sorting, keep clock = 0. For each job, add clock to the total waiting time (that is how long this job waited), then advance clock by its burst time. Divide by n at the end. Sorting dominates at O(n log n); the sweep is linear. Note this is the non-preemptive, all-arrive-at-zero version — with staggered arrival times the problem becomes preemptive SJF and needs a 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.