Greedy algorithms are seductive. They are simple and fast. But they can be subtly wrong. In the last section, you saw that greedy works for some problems and fails for others. How do you know which is which before submitting your solution? Without a proof, you might pass sample tests but fail on edge cases.
In this section, I will teach you two proof techniques that let you verify greedy correctness. By the end, you will be able to prove your greedy solutions work or find counterexamples when they do not.