Greedy Algorithms: When Local Choices Add Up

Backtracking and DP both explore many possibilities before committing to an answer - backtracking by trying and undoing, DP by solving every relevant subproblem. Greedy algorithms take the opposite bet: make the choice that looks best *right now*, commit to it permanently, and never look back. That is a much cheaper strategy - but it is only correct for problems with a specific structure, and knowing how to tell the difference is the real skill this chapter builds.

A problem has the greedy-choice property if a locally optimal choice at each step - made without reconsidering it later - always leads to a globally optimal overall solution. This is a strong claim, and it does not hold for every problem that "feels" greedy; it needs to be true of the specific problem's structure, ideally provably so, not just assumed because a greedy approach is simple to write.

The classic example where greedy provably works: given a list of (start, end) intervals representing activities, what is the maximum number of non-overlapping activities you can attend? Sorting by end time (not start time, and not by duration) and greedily taking every activity that starts at or after the end of the last one taken is optimal. The intuition: whichever activity finishes earliest leaves the most remaining time for everything after it, and it can be shown that some optimal solution always includes that earliest-finishing activity - so choosing it can never be a wrong move.

Greedy is not a universal hammer. A well-known counterexample: making change with coins [1, 3, 4] for an amount of 6. Greedily always taking the largest coin that fits picks 4, then is left with 2, which it can only fill with 1 + 1 - three coins total (4 + 1 + 1). But the true optimal answer uses just two coins: 3 + 3. Greedy fails here because this particular coin system is not "canonical" - taking the biggest coin first does not always lead to the fewest total coins. This is exactly why greedy needs the greedy-choice property proven (or at least strongly justified) for the specific problem at hand, rather than assumed by default.

Coin systems like standard currency denominations (1, 5, 10, 25, ...) are "canonical" - for these specific denominations, always taking as many of the largest coin as possible, then recursing on the remainder, does produce the minimum coin count, unlike the [1, 3, 4] counterexample above. Assuming a canonical system, the greedy approach is both simpler and faster than the dp-based coin_change from the previous module - it needs no table, just a running division against each coin from largest to smallest.

• -Greedy-choice property: a locally best choice, made once and never revisited, must always be extendable to a globally optimal solution.
• -Activity selection sorted by end time is a textbook example where this property provably holds.
• -Coin systems are not all canonical - [1, 3, 4] for amount 6 is the standard counterexample where greedy gives 3 coins but the optimum is 2.
• -When greedy fails, dynamic programming (the previous two modules) is the fallback that always finds the true optimum, at the cost of more time and space.