📜 WAYPOINT LESSON
Checkpoint — Prove, Then Sort
⭐⭐⭐ advanced⏳ 25 min read📍 Lesson 221 of 281
Minimize maximum lateness: the EDS exchange proof is the theorem; the W is the plausible SPT order that ignores deadlines and loses on adversarial inputs.
Checkpoint — Prove, Then Sort. Minimum possible maximum lateness is achieved by earliest-deadline-first — proven by the adjacent-swap exchange (d swapping two consecutive out-of-order jobs never raises max lateness). The W sorts by processing time: deadline-blind, provably suboptimal, and the full-scale test measures the gap. The discipline: the sort key is a theorem claim; only the exchange argument makes it safe.