Minimum Waiting - Exchange Proof

Proof: Consider any order that is not sorted by service time. There must be adjacent people $i$ and $j$ where $t_i > t_j$ but $i$ comes before $j$. Swap $i$ and $j$.

Before swap: $j$ waits for $i$ to finish (adds $t_i$ to $j$'s waiting time). After swap: $i$ waits for $j$ to finish (adds $t_j$ to $i$'s waiting time). Since $t_j < t_i$, the swap reduces total waiting time. Keep swapping until sorted. Each swap improves or maintains total. So sorted order is optimal.