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

Scheduling

• Sort by start time

• Sort by end time

• Sort by task size

• Sort by minimal conflict

Questions

Task Scheduling

• Meeting Rooms

• Overlapping Intervals

• CPU Task Scheduling

Sequence

• Jump Game I&II

• Sell Stock

Graph

• MST

• Dijkstra Algorithm