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