47. When does a greedy algorithm give the optimal answer?
MediumGreedy algorithms
Technical
Show model answer
A greedy algorithm makes the locally best choice at each step without revisiting it. It is optimal when the problem has the greedy-choice property (some optimal solution starts with the greedy choice) and optimal substructure. Prove it with an exchange argument.
Examples that work: activity selection (earliest finish time), Huffman coding, Dijkstra, and Kruskal/Prim. Examples that fail: coin change with arbitrary denominations and 0/1 knapsack, which need dynamic programming.