Greedy Algorithms: When Local Choices Are Globally Optimal (and When They Aren't)

In plain words

Imagine packing a bag for a hiking trip with limited weight. A greedy hiker grabs the most useful item first, then the next most useful, and keeps going until the bag is full — never reconsidering earlier choices. Sometimes this works perfectly (if everything is infinitely divisible, always grab the highest-value-per-gram item). Sometimes it's catastrophically wrong (if you grab a heavy item that's slightly better per gram, you might have no room left for two lighter items that together were worth twice as much).

A greedy algorithm builds a solution one step at a time, always taking the choice that looks best *right now*, and never reconsidering. When it works, it's wonderful: simple, fast, often O(n log n) or better. When it doesn't, it fails silently — producing a plausible but suboptimal answer. So the central skill isn't writing greedy code (that's easy) but *knowing when greedy is correct*. This lesson gives you both the classic success stories and the tools to prove — or disprove — greediness for a new problem.

The two properties that make greedy work

• Greedy-choice property: you can reach a globally optimal solution by making locally optimal choices. Crucially, a greedy choice made now is never something you'd have to undo later — it's part of *some* optimal solution.
• Optimal substructure: an optimal solution to the whole problem contains optimal solutions to its subproblems (also required for dynamic programming — the difference is that greedy commits to one choice without exploring alternatives, while DP considers all of them).

The honest truth: for most problems, greedy is *wrong*, and proving it's right for a specific problem requires an actual argument (below). The minimum spanning tree algorithms from Lesson 18 were greedy and provably optimal via the cut property — a template for how these proofs go.

Classic success: interval scheduling

Given activities with start and end times, select the maximum number that don't overlap. The greedy rule that works: always pick the activity that finishes earliest among those still compatible.

1. Sort activities by finish time.
2. Select the first (earliest-finishing) activity.
3. Scan the rest; select each activity whose start time is ≥ the last selected activity's finish time.

Activities (sorted by finish time):
  A: [1───3]
  B:   [2────5]
  C:        [4──6]
  D:           [5──────9]
  E:                [7──10]
  F:                  [8────12]

Greedy (earliest finish):
  Select A (finishes at 3) ✓
  B starts at 2 < 3 (last finish) → skip
  Select C (starts at 4 ≥ 3, finishes at 6) ✓
  D starts at 5 < 6 → skip
  Select E (starts at 7 ≥ 6, finishes at 10) ✓
  F starts at 8 < 10 → skip

Result: {A, C, E} — 3 activities  ✓ (optimal)

Wrong rule — earliest START:
  Select A [1─3], then B [2─5] conflicts, take C [4─6], then D [5─9]...
  picks fewer non-overlapping activities on many inputs.

Wrong rule — shortest DURATION:
  A[1-3]=2, B[2-5]=3, C[4-6]=2, D[5-9]=4, E[7-10]=3, F[8-12]=4
  picks A(dur 2), C(dur 2), E(dur 3) = 3 — accidentally works here but fails in general.

Why earliest-finish is optimal (exchange argument). Suppose an optimal solution doesn't start with the earliest-finishing activity. Swap its first activity for the earliest-finishing one: the earliest-finishing activity ends no later, so it can't conflict with anything the optimal solution scheduled afterward — the swapped solution is still valid and just as large. Repeating this argument shows a greedy solution matching the optimal size always exists. This *exchange argument* — 'transform any optimal solution into the greedy one without making it worse' — is the standard way to prove greedy correctness. O(n log n), dominated by the sort.

Classic success: Huffman coding

Huffman coding builds an optimal prefix-free code for data compression: frequent symbols get short bit-codes, rare ones longer. The greedy rule: repeatedly merge the two least-frequent nodes into a subtree (using a priority queue / min-heap), until one tree remains. The resulting code provably minimizes total encoded length — another greedy choice (merge the two rarest) that's globally optimal, provable by an exchange argument. O(n log n).

Symbols and frequencies:
  A:45  B:13  C:12  D:16  E:9  F:5

Min-heap initially: [F:5, E:9, C:12, B:13, D:16, A:45]

Step 1: merge F(5) + E(9) → node FE(14)
  Heap: [C:12, B:13, FE:14, D:16, A:45]

Step 2: merge C(12) + B(13) → node CB(25)
  Heap: [FE:14, D:16, CB:25, A:45]

Step 3: merge FE(14) + D(16) → node FED(30)
  Heap: [CB:25, FED:30, A:45]

Step 4: merge CB(25) + FED(30) → node CBFED(55)
  Heap: [A:45, CBFED:55]

Step 5: merge A(45) + CBFED(55) → root(100)

Resulting codes (left=0, right=1):
  A: 0        (1 bit  — most frequent)
  C: 100      (3 bits)
  B: 101      (3 bits)
  F: 1100     (4 bits)
  E: 1101     (4 bits)
  D: 111      (3 bits — less frequent)

Greedy choice (merge two rarest) is provably optimal — exchange argument shows
swapping any other pair of nodes to merge first doesn't reduce total encoded length.

The instructive failure: 0/1 knapsack vs fractional

This contrast is the best way to internalize when greedy works. Fractional knapsack (you may take fractions of items) *is* greedy-solvable: sort by value-to-weight ratio and greedily take the densest items, splitting the last one to fill the bag exactly — provably optimal. But 0/1 knapsack (each item is all-or-nothing) is *not*: greedily taking the densest item can leave the bag unable to be filled optimally. A tiny counterexample — a bag of capacity 10 with items {value 60/weight 10}, {value 50/weight 5}, {value 50/weight 5} — greedy takes the density-6 first item for value 60, but the optimal is the two 50s for value 100. The all-or-nothing constraint destroys the greedy-choice property, and 0/1 knapsack needs dynamic programming (Lesson 25). Same-sounding problem, opposite answer.

Bag capacity: 10

Items:
  Item 1: value=60, weight=10  → density = 6.0  (highest!)
  Item 2: value=50, weight=5   → density = 10.0
  Item 3: value=50, weight=5   → density = 10.0

Greedy (highest density first):
  Take Item 2 (density 10, weight 5) → remaining capacity = 5
  Take Item 3 (density 10, weight 5) → remaining capacity = 0
  Total value = 100  ✓

Wait — greedy by density picks Items 2 and 3 here.
But what if the counterexample is density-first by item 1?

  Items reordered for clearer counterexample:
  Item A: value=60, weight=10  → density = 6.0
  Item B: value=40, weight=6   → density = 6.67 ← greedy picks first
  Item C: value=40, weight=6   → density = 6.67 ← greedy picks second
  Capacity = 10

  Greedy: take B(wt=6, val=40), take C — wt=6+6=12 > 10 → can't fit
  → only B fits → total value = 40

  Optimal: take A(wt=10, val=60) → total value = 60  (greedy got 40!)

Moral: the all-or-nothing constraint means greedy can leave wasted capacity.
0/1 knapsack requires dynamic programming to consider all combinations.

Greedy vs dynamic programming

A practical strategy: when you suspect greedy, try to break it with a counterexample first. If you can't after genuine effort, attempt an exchange-argument proof. If greedy demonstrably fails, fall back to dynamic programming. Never ship a greedy solution you haven't either proven or stress-tested — 'it worked on my examples' is exactly how greedy bugs reach production.

The exchange argument: how to prove greedy is correct

The exchange argument is the standard proof template for greedy algorithms. It has three moves: (1) take *any* optimal solution OPT; (2) show you can modify OPT, step by step, to match the greedy solution without ever decreasing the objective; (3) conclude the greedy solution is at least as good as OPT — hence optimal. The key is step 2: when greedy makes a choice that OPT doesn't, swap OPT's choice for greedy's choice and argue the swap doesn't hurt. For interval scheduling: OPT's first activity ends no earlier than the earliest-finishing one → swapping it in can only free up more time → still valid and same count. The proof is local — one swap at a time — and composes.

Common pitfalls

• Assuming greedy works without proof. The default should be suspicion. Most problems are not greedy-solvable; verify before trusting.
• Choosing the wrong greedy criterion. Interval scheduling works by *earliest finish*, not shortest duration or earliest start — those give wrong answers. The right greedy rule is often non-obvious.
• Confusing similar problems. Fractional knapsack is greedy; 0/1 knapsack is not. Coin change is greedy for some coin systems (like standard currency) and *not* for arbitrary ones. The details decide.
• Skipping the counterexample check. A single failing case disproves greediness instantly and saves you from a subtly wrong solution.
• Forgetting greedy needs optimal substructure too. Without it, even a correct-looking local rule won't compose into a global optimum.

Practice problems

1. Jump game: given an array where each element is your max jump length, determine if you can reach the last index. Greedy: track the farthest reachable index. O(n).
2. Gas station: given gas and cost arrays around a circular route, find the starting station from which you can complete the circuit. Greedy: start wherever the running tank goes negative, reset there. O(n).
3. Assign cookies: greedy assign the smallest sufficient cookie to the least greedy child first — sort both, two-pointer assign. O(n log n).

Key takeaways

• Greedy makes the locally best choice and never backtracks — fast and simple when correct.
• It's optimal only with the greedy-choice property and optimal substructure; most problems lack them.
• Prove correctness with an exchange argument (transform any optimal solution into the greedy one without loss) or find a counterexample to disprove it.
• Interval scheduling (earliest finish), Huffman coding, MST, and Dijkstra are provably-optimal greedy successes.
• 0/1 knapsack is the canonical greedy failure that needs dynamic programming — same shape as fractional knapsack, opposite result.

When greedy fails because choices interact, you need to consider all of them without exponential blowup. That's the most powerful (and most feared) paradigm: dynamic programming, next. Practice spotting greedy-able problems in the **AI Learning app**.

AI Learning: AI/ML/DS Q&A

A private, offline app to learn Artificial Intelligence, Machine Learning & Data Science at your own level: ~10,000 Q&A, illustrated guides, cheat sheets, quizzes and mock tests.

Coming soon toGoogle Play