an exchange argument
How do you prove that grabbing the locally best thing really gives the best overall answer, when there are astronomically many answers to compare? You do not enumerate them. Instead you argue: take ANY optimal answer that disagrees with the greedy one, and show you can edit it, swapping one of its choices for the greedy choice, without making it worse. An exchange argument is exactly this swap-without-loss move.
Here is the skeleton. Let G be the greedy solution and O be an optimal solution. Look at the first place they differ. Construct a new solution O' from O by replacing O's choice at that spot with G's choice, while keeping O otherwise intact. Prove two things: (1) O' is still feasible (a legal solution), and (2) O' is no worse than O. Since O was optimal, O' is optimal too — and O' agrees with G in one more place than O did. Repeat, and you transform O step by step into G without ever losing optimality, so G is optimal. Concretely for minimizing lateness with deadlines, if an optimal schedule has two adjacent jobs out of deadline order, swapping them does not increase the maximum lateness, so some optimal schedule is sorted by deadline — which is exactly what greedy does.
Exchange arguments are the workhorse proof technique for greedy correctness, used for interval scheduling, minimizing lateness, Huffman coding, and the matroid theory beneath Kruskal's MST. Two pitfalls to respect: you must check the swap keeps the solution feasible (legal), and you must check it does not worsen the objective — skipping either step is the most common way these proofs silently break. When no valid exchange exists, that is often a signal greedy is wrong for the problem.
Minimizing maximum lateness: claim that scheduling jobs in increasing deadline order is optimal. Take any optimal schedule with an inversion — two adjacent jobs i before j where deadline(i) > deadline(j). Swap them. The swap can only lower the lateness of the pair and changes nothing else, so the schedule stays optimal. Remove inversions one by one until the order is exactly greedy's.
Swap an out-of-order adjacent pair: feasibility is preserved and the objective does not get worse, so optimality survives the edit.
An exchange argument must verify BOTH that the swap stays feasible and that it does not worsen the objective. Proving only one of the two is the classic broken-proof mistake.