Scheduling problems are the natural home of the exchange argument: assume an optimal schedule, show that swapping two adjacent jobs into your greedy order never makes it worse, conclude your order is optimal.
- Interval Scheduling — max non-overlapping intervals
- Weighted Interval Scheduling
- Interval Partitioning — minimum rooms
- Job Sequencing with Deadlines
- Minimising Maximum Lateness
- Exchange Arguments — the proof technique itself
- Lawler’s Algorithm (precedence constraints)
- Hu-Tucker · Huffman Coding
- Load Balancing and Makespan
See also: Greedy · Exchange Arguments