Greedy Algorithm

Note: not very important for interview

Intro

Think greedy. Maximize when you get a chance

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

Sell Stock

MST