Greedy
Make locally optimal choices at each step, proving they lead to a globally optimal solution.
- • Optimal substructure + greedy choice property
- • Activity selection
- • Huffman coding
- • Fractional knapsack
- • Local optimum doesn't guarantee global optimum
- • Need to consider all combinations (use DP)
- • Assuming greedy works without proof
- • Wrong sorting criterion
- • Not handling ties correctly
Key Invariant
A greedy algorithm works only if the locally optimal choice is also globally optimal — prove it or use DP