Skip to content
Tutorials Center
My learning

Topics

Lesson 167 of 225 ยท Greedy Algorithms

Greedy Algorithms

Understand greedy algorithms in Python: the greedy choice property, exchange-argument proofs, coin change counterexamples and how to test a greedy idea.

Imagine you are handed change at a shop. The cashier does not try every combination of coins. They take the biggest coin that still fits, then the biggest that fits in what remains, and so on. It is fast, it needs no planning, and for ordinary coins it gives the fewest coins possible.

That is a greedy algorithm: build the answer one step at a time, and at each step take the option that looks best right now, never reconsidering. When it works, greedy is the simplest and fastest kind of algorithm, often O(n log n) from a single sort. The catch is that it does not always work, and a wrong greedy looks just as convincing as a right one. The real skill is knowing when greedy is correct and how to check it.

Two properties that make greedy correct

A greedy algorithm is correct when the problem has both of these properties.

1. Greedy choice property. There is always an optimal solution that contains the greedy first choice. In other words, taking the locally best option never rules out the global best.

2. Optimal substructure. After you make that choice, what remains is a smaller instance of the same problem, and an optimal solution to the remainder, combined with your choice, is optimal overall. (This is the same property that dynamic programming needs.)

The difference between the two techniques is what happens at a decision. DP keeps all the options open, computes every subproblem and picks the best. Greedy commits to one option and never looks back. That is why greedy is faster, and why it is riskier. The lesson Greedy vs Dynamic Programming compares them on the same problems.

TEXT
DP:      decision -> try every option -> solve each subproblem -> take the best
Greedy:  decision -> pick the option that looks best -> continue (no going back)

Example: making change, and when it breaks

Fewest coins to make an amount, coins available in unlimited supply. The greedy rule: always take the largest coin that does not exceed the remaining amount.

Python Greedy change versus optimal change

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For the US system, greedy is optimal. For {4, 3, 1} and amount 6, greedy takes 4 first and then needs 1 + 1 (three coins), while 3 + 3 uses two. The first greedy choice (take the 4) is not contained in any optimal solution, so the greedy choice property fails. A single counterexample is enough to disprove a greedy idea. You can see the correct approach in coin change.

How to find out if greedy works

You have three practical tools, from cheap to rigorous.

Tool 1: test it against a brute force

Write the slow, obviously correct version (DP or try-everything), generate many small random inputs, and compare. If the two ever disagree, print the input: it is your counterexample. A few minutes of testing beats an hour of hoping.

Python Find the smallest counterexample for a coin system

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Testing finds bugs but cannot prove correctness. Systems where each coin divides the next (like {8, 4, 1}) are always safe for greedy, and the real US coins happen to be safe too, but there is no simple rule for arbitrary denominations.

Tool 2: the exchange argument

The standard proof technique for greedy: take any optimal solution and show you can swap pieces of it, one at a time, to make it agree with the greedy choice without making it worse. If you can, then the greedy choice is part of some optimal solution.

A worked example: shortest job first. You have jobs with known durations to run one after another on one machine. Minimise the total waiting time (the sum, over jobs, of the time each job waits before it starts).

The greedy rule: run the shortest job first. Why is it optimal?

TEXT
Suppose an optimal order has two neighbours in the "wrong" order:
   ... [long job L] [short job S] ...   with L > S

Every job before them is unaffected by their order.
Every job after them is unaffected too (L + S is the same total).
Swap them -> ... [S] [L] ...
   S now waits less by L   (S no longer waits for L)
   L now waits more by S   (L now waits for S)
   net change = S - L < 0   -> waiting time DROPPED

So any order with a long job directly before a short one can be improved.
Repeat until no such pair remains: the jobs are sorted shortest first.

That sketch is a real proof: an optimal solution can be reshaped into the greedy one at no cost.

Python Shortest job first beats every order

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Tool 3: "greedy stays ahead"

Another proof style: show that after each step, the greedy solution is at least as good as any other solution's progress after the same step. For activity selection (next lesson, Interval Scheduling) this means "greedy's i-th chosen activity finishes no later than the i-th activity of any optimal solution", so greedy can fit at least as many.

Greedy that fails: 0/1 knapsack

A thief has a bag of capacity 10 and can take each item once. A tempting greedy: take items in decreasing value-per-weight order.

Python Value per weight fails for 0/1 knapsack

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The ratios are 6, 5 and 4, so greedy takes the first two items (value 160) and has 20 units of capacity left that nothing fits into. The optimum skips the best-ratio item and takes the other two (value 220). The fractional knapsack, where you may take part of an item, is solved by the ratio rule, because you can fill the gap exactly. Changing one rule of the problem flips greedy from wrong to right, which is why you must prove it per problem. See Greedy Problems.

A greedy checklist

Ask these questions before trusting a greedy idea:

  1. What is the choice at each step? Name it (pick an item, pick an interval, pick a coin).
  2. What ordering makes one choice look best? Sorting by the right key is usually the entire algorithm: finish time, deadline, ratio, difficulty.
  3. Does a smaller instance remain after the choice? If the choice changes the rules for the rest in a messy way, be suspicious.
  4. Can you write an exchange argument? Even a rough one shows whether the idea is sound.
  5. Does it survive a brute-force comparison on a few thousand small random cases?

Complexity of greedy algorithms

Most greedy algorithms are dominated by their sort: O(n log n) time. The loop after sorting is O(n). Space is O(1) extra for in-place processing, or O(n) if you keep the chosen items. Greedy built on a priority queue (see priority queues), as in Huffman coding and Dijkstra's shortest paths, costs O(n log n) from the heap operations.

Famous algorithms that are greedy at heart: Dijkstra (finalize the nearest unvisited node), Prim and Kruskal for minimum spanning trees, Huffman coding (Huffman), activity selection, and fractional knapsack.

Common mistakes

  • Trusting the first idea. "Take the biggest" and "take the cheapest" feel right and are often wrong. Test.
  • Sorting by the wrong key. In interval problems, sorting by start time, by length and by end time give three different algorithms, and only one is correct.
  • Ignoring ties. A wrong tie-break can break a proof or make output unstable. Decide what happens when keys are equal.
  • Confusing greedy with DP shortcuts. If you need to remember more than "what is left", you may need DP.
  • Not handling impossible cases. Greedy change with {5, 10} and amount 3 has no answer; return a clear signal.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does the greedy choice property say?

    If a locally best choice can be extended to an optimal solution, committing to it loses nothing.
  2. 2. Coins {4, 3, 1}, amount 6. How many coins does greedy use, and how many are optimal?

    Greedy takes 4 + 1 + 1 (three coins), but 3 + 3 needs only two.
  3. 3. In the shortest-job-first proof, what is the effect of swapping a long job immediately before a short one?

    The short job saves the long job's duration, the long job loses the short job's duration, and everything after them is unchanged.
  4. 4. Why is a successful brute-force comparison on random inputs not a proof?

    Testing can disprove a greedy idea but not prove it, so combine it with an exchange or stays-ahead argument.
  5. 5. What dominates the running time of most greedy algorithms?

    After sorting, one pass over the data is O(n).

Summary

  • A greedy algorithm commits to the locally best choice at each step and never revisits it.
  • It is correct only when the problem has the greedy choice property and optimal substructure.
  • Disprove a greedy idea with one counterexample (coins {4, 3, 1}, 0/1 knapsack by ratio); prove it with an exchange argument or "greedy stays ahead".
  • Test greedy against a brute force or DP on many small random inputs before trusting it.
  • Typical cost: O(n log n) for the sort plus an O(n) pass.
  • Slightly different rules change the answer: fractional knapsack is greedy, 0/1 knapsack is not.

Next: Interval Scheduling and Meeting Rooms