A greedy algorithm builds a solution piece by piece, always making the choice that looks best right now — never reconsidering earlier decisions.

• When it works — dramatically simpler than DP.
• When it doesn’t — it can produce arbitrarily bad answers.

The Greedy Choice Property

For a greedy algorithm to be correct, the problem must have the greedy choice property: there is always an optimal solution that includes the locally optimal first choice. Combined with optimal substructure (the rest of the problem after a greedy choice is a smaller instance of the same kind), this justifies the approach by induction.

Classic greedy successes:

• Activity Selection — always pick the activity that finishes earliest.
• Fractional Knapsack — always take the highest value/weight ratio.
• Huffman Coding — always merge the two lowest-frequency nodes.
• Prim’s / Kruskal’s MST — always add the cheapest safe edge (cut property).
• Dijkstra’s — always relax through the closest unvisited node.

Proving Greedy Is Correct

The standard proof tool is the exchange argument: take any optimal solution and show you can swap in your greedy choice without making it worse. If the swap can be repeated, there is an optimal solution containing every greedy choice.

A second tool is the matroid: when the problem’s feasible sets form a matroid, the greedy algorithm is provably optimal. MST (graphic matroid) is the canonical example.

A Worked Exchange Argument: Activity Selection

This is the argument you’d reproduce for any greedy proof. Activity selection: given intervals [start, end), pick the maximum number of non-overlapping activities. Greedy rule: always take the activity with the earliest finish time, then recurse on everything that starts after it.

Claim. There is an optimal solution containing the activity with the earliest finish time, say g.

Proof. Take an optimal solution OPT and let a be its first activity. Two cases:

1. a = g — done.
2. a ≠ g. Since g finishes no later than a (earliest finish), and a starts the schedule, swap a for g: replace a with g in OPT. Every other activity in OPT starts after a ends, hence after g ends (because g.end ≤ a.end) — so the swap keeps the schedule valid. The new schedule still has |OPT| activities and starts with g.

The swap didn’t shrink the optimum, and it can be repeated: remove g, apply the same argument to the remaining problem (which is the same kind of instance — that’s optimal substructure), and by induction there’s an optimal solution containing the greedy choice at every step. Hence greedy is correct.

Why the structure matters. The proof works because the only constraint between activities is non-overlap — replacing an early activity with an even-earlier one can’t break anything. For problems where choices interact more (0/1 knapsack, TSP), the analogous swap does break feasibility, and that’s precisely why greedy fails there.

When Greedy Fails

Greedy is not universal. The failure mode: local choices block future, better combinations.

• 0/1 Knapsack — taking the best-ratio item first can consume capacity needed by a higher-value pair.
• Coin Change with arbitrary denominations — always taking the largest coin can overshoot the true minimum.
• Traveling Salesman — nearest-neighbor tours can be far from optimal.

The pattern: greedy fails when the problem needs lookahead — when the value of a choice depends on which other choices remain.

Greedy vs DP

If you suspect greedy, first prove (or test) the greedy choice property. When in doubt, DP is the safe fallback that always explores the full space.

Practice Trajectory

Start with interval problems (activity selection, minimum platforms), then ratio problems (fractional knapsack, optimal merge patterns), then graph algorithms (Prim, Kruskal, Dijkstra), and finally matroid-flavored problems. For every problem, ask: “can a locally optimal choice ever block the global optimum?”