A lesson from the Algorithms & Patterns module of the bootcamp. About an 11 minute read.
Take the best-looking option right now and never look back. When it works, it is the fastest and shortest solution there is. The difficulty is that greedy algorithms LOOK right far more often than they ARE right. So this lesson is less about the technique and more about the habit of proving it before you trust it, and recognizing what a counterexample looks like.
At each step, commit to the option that looks best right now and move on. No going back, no table, usually one sort and one sweep. Greedy is only correct when the problem has the GREEDY CHOICE PROPERTY: some optimal solution contains the greedy choice, so taking it never costs you the best answer. The way to prove that is an exchange argument, and it is short enough to produce on the spot. Take any optimal solution, assume it does not contain your greedy choice, and show you can swap your choice in without making the solution worse. If the swap always works, greedy is optimal. If you cannot make the swap work, you have almost certainly found the shape of a counterexample instead, which is just as useful.
The rest of this lesson continues with 4 further sections. See the full curriculum.
Browse all 576 practice puzzles