Greedy Algorithms: The Exchange Argument & Classic Problems

A greedy algorithm builds a solution by repeatedly taking the locally best choice; it is optimal exactly when the problem has the greedy-choice property plus optimal substructure, proved by an exchange argument.