Greedy Algorithm

Intro

Think greedy. Maximize when you get a chance. A greedy solution can be hard to come up.

Two Ways to Prove Greedy Optimal

• Optimal Argument
  • Comparing to the optimal solution greedy always stays ahead
  • If they are different, prove why greedy is better
• Exchange Argument
  • Exchange (swap) out element in O (switch order or remove/insert element)
  • Argue the solution is no worse than before
  • In the end, there is no difference b/w O and A

Examples

Jump Game I&II

Sell Stock

MST