Trees, graphs and optimization
Greedy reasoning
Prove a local decision preserves an optimal solution.
Understand the problem
A greedy algorithm needs an exchange argument or another correctness proof. Identify a choice that can replace the first decision of an optimal solution without making it worse.
Make it concrete
For maximum non-overlapping meetings, choose the earliest finishing compatible meeting.
Trade-offs and pitfalls
A plausible local heuristic can fail when choices interact globally.
Check your understanding
Give a counterexample to choosing the shortest meeting first.
Practice this topic