Proof: Consider any order that is not sorted by service time. There must be adjacent people and where but comes before . Swap and .
Before swap: waits for to finish (adds to 's waiting time). After swap: waits for to finish (adds to 's waiting time). Since , the swap reduces total waiting time. Keep swapping until sorted. Each swap improves or maintains total. So sorted order is optimal.