A lesson from the data structures and algorithms bootcamp. About a 11 minute read.
Take the best-looking option right now and never reconsider. When it works it is the fastest and shortest solution there is. The difficulty is entirely that greedy algorithms LOOK right far more often than they ARE right, so this lesson is less about the technique than about the habit of proving it before you trust it, and about recognising the shape of a counterexample.
At each step, commit to the locally best option and move on. No backtracking, no table, usually one sort and one sweep. Greedy is correct only when the problem has the GREEDY CHOICE PROPERTY: there exists an optimal solution that contains the greedy choice, so taking it never costs you the best answer. The way to establish 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 construct the swap, you have almost certainly found the shape of the counterexample instead, which is just as useful.
The rest of this lesson continues with 4 further sections. See the full curriculum.
Browse all 536 practice puzzles