Two Proof Techniques

I will teach you two main techniques for proving greedy correctness:

$1.$ Exchange argument: : Show that any optimal solution can be transformed into the greedy solution without losing quality.

$2.$ Stays ahead argument: : Show that at every step, the greedy solution is at least as good as any alternative. Both techniques are powerful. The right choice depends on the problem structure. I will show you when to use each one. Most interview greedy problems can be proven with one of these two techniques.