A strong answer
One server handles n jobs with durations p₁ … pₙ, one at a time. A job's finishing time is the sum of the durations of everything up to and including it; the goal is to minimize the sum of finishing times (the exchange argument), which also minimizes average waiting.
Take any order and two adjacent jobs, a then b, with a longer than b. Swap them. Jobs before the pair are unaffected. Jobs after it are also unaffected, because the pair occupies the same total time in either order. Only the pair changes: b finishes a units earlier and a finishes b units later, so the total changes by b − a, which is negative. So any order with a longer job immediately before a shorter one can be strictly improved.
An order with no such adjacent pair is sorted by duration. Starting from an optimal order, repeated swaps never make it worse and end at the sorted order, so the sorted order is optimal too (ties don't matter). Considering adjacent swaps suffices because any order can be sorted by them, as bubble sort does.
With weights, the same swap changes the total by w_a·p_b − w_b·p_a, so a should come first when w_a/p_a ≥ w_b/p_b: sort by the ratio of weight to duration, Smith's rule. In operating systems, pure shortest-job-first can starve long jobs and requires knowing durations in advance, so real schedulers estimate them and add aging. When jobs arrive over time, the optimal preemptive rule is shortest remaining time first.
What the interviewer is listening for
- A precise objective.
- The adjacent-swap computation, including why other jobs are unaffected.
- The step from "every inversion can be improved" to "sorted is optimal".
- The weighted generalization.
Common mistakes
- Asserting that short jobs first helps without the swap argument.
- Forgetting that the swap must not hurt the jobs after the pair.
- Sorting by weight alone in the weighted version.