- For greedy algos, we always make a choice that we would never regret, it’s always the next best choice. Everything before is good, and everything in the future will also be good
- unlike backtracking
- can be proven by contradiction
- We know that there exists a set of choices that gives us an optimal solution
- Given that optimal solution, assume yr at a point where you just messed up the extension (and in turn the optimal solution) using the greedy algo
- What we know:
- prefix & postfix is valid (overlap for interval scheduling proof)
- prefix and greedy choice in question is a valid choice
- by the design (conditions) of our algo
- ~30: I speak
- 35: greedy choice and postfix is valid
- because our algo(greedy) picks the best (earliest) which we know exists