vizlearn
Home / Algorithms

Greedy Algorithms

Algorithms & Data StructuresBy Updated

Always take the best-looking option right now and never reconsider. Sometimes that is provably optimal; sometimes it walks you straight past the right answer — and this lab shows you both.

Controls

Greedy Choices

step 0

Insight

A greedy algorithm makes the locally best choice at each step and never backtracks. It is fast and simple — but only correct when the problem has the right structure.

greedy result–
true optimum–
verdict–

Complexity

Greedy (sorted) O(n log n)
DP alternative O(n·W)
Space O(1)

Overview

Greedy algorithms build a solution one local choice at a time. They are often fast and simple, but a plausible local choice can block a better complete answer. The key task is proving the rule works for the specific problem.

When a greedy rule is valid

Two useful proof ideas are the greedy-choice property—some optimal solution begins with the locally best choice—and optimal substructure—after that choice, the remaining task is a smaller instance of the same problem. A proof may use an exchange argument: replace the first choice in an optimal solution with the greedy choice and show the solution is no worse.

ProblemGreedy ruleResult
Activity selectionChoose the compatible activity that finishes earliestOptimal maximum-size schedule
Fractional knapsackTake the greatest value per unit weightOptimal when items can be split
Minimum spanning treeAdd a cheapest safe edgeKruskal’s and Prim’s algorithms are optimal
Shortest pathsFinalise the nearest unsettled vertexDijkstra is correct only with non-negative edges
0/1 knapsackTake the greatest value-to-weight ratioCan fail because items cannot be split

These are problem-specific proofs. “Always take the largest” or “always choose the cheapest” is not a general correctness argument.

A worked success: choosing activities

Suppose activities have start and finish times, and only one can run at once. Sort by finish time; repeatedly select the first activity that starts after the last selected one finishes. This leaves as much time as possible for whatever follows.

Why is that safe? Consider an optimal schedule whose first activity finishes later than the earliest-finishing compatible activity. Replacing it with the earlier finisher cannot reduce the number of later activities that fit. Repeating the exchange establishes an optimal schedule that follows the greedy rule. The sorting costs O(n log n); the scan costs O(n).

Choosing the earliest start or shortest duration does not give the same guarantee. One long early-starting activity can block several short non-overlapping activities, and a short activity can straddle two that could otherwise both be chosen.

A counterexample: coin change

Greedy coin change repeatedly takes the largest coin no bigger than the remaining amount. With coins {1, 3, 4} and amount 6, it chooses 4, then 1, then 1: three coins. The optimum is 3 + 3: two coins. The local choice is legal but not globally best.

The result depends on the denomination system. Some systems have a proof that greedy is optimal; arbitrary systems do not. Dynamic programming can solve the minimum-coin version for a bounded integer amount by comparing choices across subamounts; see dynamic programming.

Try the visualiser

  1. Choose Problem “Activity selection (greedy works)” and step through the schedule. Check that each accepted activity starts after the previous one finishes.
  2. Choose Problem “Coin change — greedy FAILS” and set amount to 6. With coins {1, 3, 4}, compare the greedy choices with the two-coin optimum.

The experiment makes a useful distinction visible: the same simple pattern can be optimal on one problem and fail on another.

Where greedy appears

Huffman coding repeatedly merges the two least-frequent symbols to build an optimal prefix code. Kruskal and Prim use safe-edge choices to build a minimum spanning tree. Dijkstra selects the nearest unsettled vertex, provided every edge weight is non-negative. Fractional knapsack works because taking part of an item is allowed. For each algorithm, its correctness depends on its own invariant or exchange proof.

Sources and next steps

For shortest paths, continue with Dijkstra’s algorithm and Bellman–Ford. For a local-choice proof, compare the activity-selection argument above with dynamic programming, which keeps alternatives when a local choice is not safe.

Run it in Python

Two greedy algorithms: one that is provably optimal and one that is confidently wrong, on inputs that differ only in the coin denominations. Both are checked against an exhaustive answer in the same run.

greedy.pyPython 3
Output
How the code works
  1. for c in sorted(coins, reverse=True):The greedy choice: largest coin that still fits. It is optimal for British, US and euro denominations, and that familiarity is exactly why people assume it is optimal in general.
  2. ([1, 3, 4], 6)The counterexample. Greedy takes 4 + 1 + 1; two 3s would do. Nothing about the algorithm changed — only the denominations — and it fails silently, with a plausible-looking answer.
  3. optimal_coins(...)A dynamic programming check run alongside, so the verdict is computed rather than asserted. This is also the practical test for whether a greedy idea is safe: compare it to brute force on small inputs.
  4. sorted(meetings, key=lambda m: m[2])   # by ENDSorting by finish time is what makes activity selection provably optimal: taking the meeting that frees the room earliest can never shut out a better schedule. There is a real exchange argument behind that, and it is what separates this from the coin case.
  5. sorted by m[1]   # by STARTThe same greedy structure on a different key, and it loses immediately — one long early meeting blocks several short ones. Greedy is not a strategy on its own; the choice of key is the algorithm.
Change one thing
  • Find another denomination set where greedy fails. They are easy to construct once you look for a coin that is more than twice the one below it.
  • Sort the meetings by duration instead. Shortest-first sounds reasonable and is also wrong; build the input that breaks it.
  • Add a meeting that spans the entire day. Both strategies now have to reject something, and only one of them rejects the right thing.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.




Predict, then reveal
About to run: set amount to its maximum (20). Before it does — what happens to the readout?
Committing to an answer first is the point — the reveal runs the experiment on the visualisation above and reads the real value back, so nothing here is scripted.
Check yourself
0 of 3
Answer without scrolling back up.
  1. Greedy coin change works for [1, 5, 10, 25] but fails for [1, 3, 4]. What does that show?
  2. Activity selection is provably optimal when the meetings are sorted by:
  3. The practical way to test a greedy idea is to:





 Cheat sheet
Greedy Algorithms
Take the locally best option at each step and see when that greedy choice is provably optimal — and when it quietly fails.
ALGORITHMS · vizlearn.in/dsa/greedy_algorithms.html
More in Algorithms
AlgorithmsBacktracking Search MethodAlgorithmsDynamic ProgrammingAlgorithmsKMP String MatchingAlgorithmsBig-O Notation and Time Complexity
About the author
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.
About VizLearnGitHubLinkedInContact