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
amount6
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 alternativeO(n·W)
SpaceO(1)
Greedy Algorithms
Fast, simple, and wrong just often enough to be dangerous.
Before the details
A greedy algorithm builds a solution one step at a time, always taking whatever looks best at that moment, and never revisiting a decision. No backtracking, no lookahead.
When greedy is provably correct
Two properties are needed:
Greedy choice property. A locally optimal choice is part of some globally optimal solution.
Optimal substructure. After making that choice, the remaining problem is a smaller instance of the same problem.
Where both hold, greedy is optimal and faster than dynamic programming. Where the first fails, greedy gives an answer that may be arbitrarily bad.
Problem
Greedy optimal?
Activity selection (earliest finish time)
Yes
Huffman coding
Yes
Minimum spanning tree (Kruskal, Prim)
Yes
Dijkstra's shortest path
Yes, with non-negative weights
Fractional knapsack
Yes
0/1 knapsack
No — needs DP
Coin change, arbitrary coins
No — needs DP
Travelling salesman
No — and greedy is a common heuristic
The knapsack pair is the clearest illustration. If items can be split, taking the best value-per-weight ratio first is optimal. If they cannot, that ratio can mislead — and the problem becomes NP-hard, needing dynamic programming for an exact answer.
Activity Selection: Greedy Wins
Given activities with start and finish times, pick the most that do not overlap. The greedy rule is: always take the one that finishes earliest among those still compatible.
Why is that safe? Finishing earliest leaves the maximum possible time for everything after it. Any optimal schedule can have its first activity swapped for the earliest-finishing one without reducing the count — that is the exchange argument, and it makes greedy provably optimal here.
Note that sorting by duration or start time both fail. The specific greedy criterion matters enormously.
Coin Change: Greedy Fails
With coins {1, 5, 10, 25} greedy works — always take the largest coin that fits. That is why it feels natural at a till.
Now switch to greedy FAILS, using coins {1, 3, 4} and amount 6. Greedy takes 4, then 1, then 1 — three coins. The optimum is 3 + 3 — two coins. Taking the biggest coin first stranded the algorithm in a worse position.
Nothing about the greedy code is buggy. The problem simply lacks the greedy choice property for that coin set, and only dynamic programming is guaranteed correct.
Famous Greedy Algorithms That Do Work
Dijkstra — always expand the nearest unvisited node. Correct only when edge weights are non-negative.
Kruskal and Prim — always take the cheapest safe edge. Provably build minimum spanning trees.
Huffman coding — always merge the two least frequent symbols. Produces optimal prefix codes.
Fractional knapsack — take the best value-per-weight first. Works because items can be split; the 0/1 version cannot, and needs DP.
Take the best option now, and never reconsider
A greedy algorithm makes the locally optimal choice at each step and never revisits it. No backtracking, no considering combinations — just the best-looking move, repeatedly.
That is dramatically cheaper than exploring alternatives, and it is only correct for problems with a particular structure.
Coin change with UK coins. Make 87p from 50, 20, 10, 5, 2, 1: take 50 (37 left), 20 (17), 10 (7), 5 (2), 2 (0). Five coins, and provably optimal.
Coin change with an awkward set. Make 30 from coins 25, 20, 1: greedy takes 25, then five 1s — six coins. The optimum is two 20s and... no. It is 20 + 1×10, also worse. With coins 25, 20, 10 and target 40: greedy takes 25 then 10 then five 1s if available; the optimum is two 20s. Greedy fails.
The difference is a property of the coin system, not of the algorithm. Greedy coin change is optimal for canonical systems (including UK and euro coins) and not in general — which is exactly the shape of the whole topic.
Activity selection: the canonical proof
Given intervals, select the largest number that do not overlap.
The correct greedy rule is earliest finish time, not earliest start or shortest duration:
def max_activities(intervals):
intervals.sort(key=lambda x: x[1]) # by end time
chosen, last_end = [], float("-inf")
for start, end in intervals:
if start >= last_end:
chosen.append((start, end))
last_end = end
return chosen
Why earliest finish works: choosing the activity that finishes soonest leaves the maximum remaining time for everything else. Any optimal solution's first activity can be swapped for this one without reducing the count — which is an exchange argument, and it is the standard way greedy correctness is proved.
Why the alternatives fail: earliest start can pick one very long activity that blocks many; shortest duration can pick one that straddles the boundary between two others.
That distinction — the right greedy criterion versus a plausible wrong one — is where most greedy mistakes live. The algorithm is trivial; the choice of what to be greedy about is the problem.
Where greedy is provably right, and where it is confidently wrong
Greedy algorithms are the ones that take the best-looking option now and never reconsider. Sometimes that is optimal and provably so; sometimes it is merely fast. The difference is a property of the problem, and running both on the same two problems makes it concrete.
example_01.pyPython
# PROBLEM 1: activity selection. Pick the most non-overlapping meetings
# from a set. Greedy by EARLIEST FINISH TIME is provably optimal here.
# "x" is the trap for earliest-start: it begins first and runs all day.
MEETINGS = [("a", 1, 5), ("b", 4, 6), ("c", 5, 10), ("d", 9, 11),
("e", 10, 15), ("f", 14, 16), ("g", 15, 20), ("x", 0, 20)]
def greedy_by(meetings, key, label):
chosen, last_end = [], -1
for m in sorted(meetings, key=key):
if m[1] >= last_end:
chosen.append(m[0])
last_end = m[2]
return label, chosen
import itertools
def brute_force(meetings):
best = []
for r in range(len(meetings), 0, -1):
for combo in itertools.combinations(sorted(meetings, key=lambda m: m[1]), r):
ok = all(combo[i][2] <= combo[i + 1][1] for i in range(len(combo) - 1))
if ok:
return [m[0] for m in combo]
return best
strategies = [
(lambda m: m[2], "earliest finish"),
(lambda m: m[1], "earliest start"),
(lambda m: m[2] - m[1], "shortest duration"),
]
print("%-20s %-30s %s" % ("strategy", "chosen", "count"))
for key, label in strategies:
_, chosen = greedy_by(MEETINGS, key, label)
print("%-20s %-30s %d" % (label, " ".join(chosen), len(chosen)))
best = brute_force(MEETINGS)
print("%-20s %-30s %d" % ("optimal (brute force)", " ".join(best), len(best)))
# Earliest-finish matches the brute-force optimum. The other two rules,
# which are every bit as intuitive, do not -- and they fail for different
# reasons. Earliest-start takes "x" because it begins at 0, and "x" runs
# until 20, so one choice consumes the entire day. Shortest-duration takes
# the short meetings, but the short ones here are precisely the ones that
# straddle two longer meetings, so each pick blocks two to gain one.
#
# "Be greedy" is not a strategy until you say greedy BY WHAT, and only one
# choice of what has a proof behind it.
#
# The proof sketch: taking the activity that finishes first leaves the
# largest possible remaining interval, so any solution can be rewritten to
# start with it without getting worse. That is an exchange argument, and
# a greedy algorithm is correct exactly when one exists.
#
# PROBLEM 2: the knapsack, where no such argument exists.
ITEMS = [("gold", 10, 60), ("silver", 20, 100), ("bronze", 30, 120)]
CAPACITY = 50
def greedy_knapsack(items, cap):
take, total, left = [], 0, cap
for name, w, v in sorted(items, key=lambda i: i[2] / i[1], reverse=True):
if w <= left:
take.append(name); total += v; left -= w
return take, total
def best_knapsack(items, cap):
best = ([], 0)
for r in range(len(items) + 1):
for combo in itertools.combinations(items, r):
w = sum(i[1] for i in combo)
v = sum(i[2] for i in combo)
if w <= cap and v > best[1]:
best = ([i[0] for i in combo], v)
return best
print()
print("0/1 knapsack, capacity %d" % CAPACITY)
g = greedy_knapsack(ITEMS, CAPACITY)
b = best_knapsack(ITEMS, CAPACITY)
print(" greedy by value/weight: %-24s = %d" % (str(g[0]), g[1]))
print(" optimal: %-24s = %d" % (str(b[0]), b[1]))
# Greedy took gold and silver -- the two best value-per-weight ratios --
# filled 30 of the 50 units, and then could not fit the 30-unit bronze.
# The optimal answer SKIPS the item with the best ratio entirely, and no
# greedy rule can do that, because greedy never reconsiders a choice.
#
# Now allow fractions of an item. Nothing else changes:
def fractional(items, cap):
total, left = 0.0, cap
for name, w, v in sorted(items, key=lambda i: i[2] / i[1], reverse=True):
take = min(w, left)
total += v * take / w
left -= take
if left == 0:
break
return total
print()
print("fractional knapsack, same items and capacity: %.0f"
% fractional(ITEMS, CAPACITY))
# Higher than either 0/1 answer, and the SAME greedy rule that failed
# above is now provably optimal -- because with fractions there is always
# an exchange that swaps a worse ratio for a better one, and that exchange
# argument is precisely what was missing in the 0/1 version.
#
# So the lesson is not "greedy is unreliable". It is that greedy is
# correct exactly when the problem admits an exchange argument, and that
# whether it does can turn on a detail as small as whether you are allowed
# to cut an item in half.
Output
Try it yourself
Run activity selection. Watch it pick the earliest finisher and reject everything that overlaps — and confirm the result matches the true optimum.
Run coin change with friendly coins. Greedy and optimal agree, which is why the approach feels obviously right.
Now run the failing case. Greedy returns 3 coins; the optimum is 2. Same algorithm, different coin set.
Slide the amount in the failing case. Some amounts greedy gets right by luck; others it does not. There is no warning — that is what makes it dangerous.
Compare the two verdicts. A greedy algorithm gives you no signal when it is wrong; you must prove correctness in advance.
In one line
Greedy algorithms are fast and elegant when the greedy choice property holds — and silently wrong when it does not. Always ask whether a locally best move can ever block a globally better one. If it can, reach for dynamic programming instead.
Greedy against dynamic programming
Greedy
Dynamic programming
Choices
One, committed
All, compared
Revisits decisions
No
Effectively yes
Typical complexity
O(n log n), often sorting-dominated
O(n×states)
Correctness
Only with the greedy choice property
General
Memory
O(1) beyond the input
O(states)
The practical procedure when facing a new optimisation problem: try to find a greedy rule and a counterexample. If a counterexample exists, use dynamic programming. If several attempts to break it fail, look for an exchange argument to prove it.
Do not assume greedy works because it produces plausible answers on small examples. That is how incorrect solutions ship — greedy failures are often subtle and appear only on specific inputs.
Greedy as an approximation
When exact solutions are intractable, greedy is frequently the best practical option and sometimes comes with a guarantee.
Set cover. Repeatedly take the set covering the most uncovered elements. NP-hard exactly, and greedy is within a factor of ln(n) of optimal — and no polynomial algorithm does substantially better.
Travelling salesman. Nearest-neighbour construction is fast and typically 25% worse than optimal. Christofides' algorithm guarantees within 50% for metric instances.
Job scheduling. Longest-processing-time-first is within 4/3 of optimal for minimising makespan on identical machines.
Huffman coding. Repeatedly merge the two least frequent symbols — and here greedy is exactly optimal, which is why it is used in every compression format.
So greedy occupies two roles: exactly optimal for a specific set of problems, and a strong fast approximation for many that are intractable. Knowing which situation you are in is the point.
Where greedy algorithms are used
Huffman coding in ZIP, JPEG, MP3 and HTTP compression.
Dijkstra's algorithm in every routing protocol and navigation system.
Minimum spanning trees for network design and clustering.
Interval scheduling in room booking, CPU scheduling and advertising slot allocation.
Cache eviction. LRU is greedy — evict the least recently used, without predicting the future.
Decision tree construction. Choosing the best split at each node is greedy, and it is why trees are not globally optimal.
The decision-tree case is a good closing example: finding the globally optimal tree is intractable, so every implementation is greedy, and everyone accepts a locally-optimal tree because it works well enough.
Questions people ask
How do I know greedy will work? Prove the greedy choice property with an exchange argument, or find a counterexample. There is no shortcut.
Is greedy always faster than DP? Usually, because it explores one path rather than a state space — often dominated by an initial sort.
What if greedy is wrong but close? That is an approximation algorithm, and it is frequently the right engineering answer for NP-hard problems.
Is Dijkstra greedy? Yes — it commits to the closest unvisited node, which is exactly why negative weights break it.
Can greedy be combined with DP? Yes — some DP solutions use a greedy rule to prune states, and some greedy algorithms use DP for subproblems.
Why does the greedy criterion matter so much? Because the algorithm is the criterion. Earliest-finish works for activity selection and earliest-start does not.
Recap in one screen
Make the locally best choice and never reconsider — cheap, and only correct with the greedy choice property.
Optimal for activity selection, Huffman coding, MST, Dijkstra and fractional knapsack.
Wrong for 0/1 knapsack, arbitrary coin systems and travelling salesman — use DP or accept an approximation.
The hard part is choosing what to be greedy about; earliest finish time works where earliest start does not.
Prove correctness with an exchange argument, or find a counterexample — do not infer it from small examples.
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
# Greedy: take the best-looking option now and never reconsider.
from itertools import combinations
def greedy_coins(coins, target):
chosen = []
for c in sorted(coins, reverse=True): # biggest first
while target >= c:
target -= c
chosen.append(c)
return chosen if target == 0 else None
def optimal_coins(coins, target):
"""Brute force, for checking the greedy answer against."""
best = [0] + [float("inf")] * target
for t in range(1, target + 1):
for c in coins:
if c <= t:
best[t] = min(best[t], best[t - c] + 1)
return best[target]
for coins, target in [([1, 5, 10, 25], 63), ([1, 3, 4], 6), ([1, 7, 10], 15)]:
got = greedy_coins(coins, target)
best = optimal_coins(coins, target)
verdict = "optimal" if len(got) == best else f"WRONG - {best} would do"
print(f"coins {str(coins):>14} target {target:>3}: greedy took {len(got)} "
f"{got} {verdict}")
# --- a greedy algorithm that is always right ---------------------------
meetings = [("a", 1, 4), ("b", 3, 5), ("c", 0, 6), ("d", 5, 7),
("e", 3, 9), ("f", 5, 9), ("g", 6, 10), ("h", 8, 11)]
def activity_selection(meetings):
chosen, finish = [], 0
for name, start, end in sorted(meetings, key=lambda m: m[2]): # by END time
if start >= finish:
chosen.append(name)
finish = end
print(f" take {name} ({start}-{end}), room free again at {finish}")
else:
print(f" skip {name} ({start}-{end}), clashes")
return chosen
print()
print("booking one room, most meetings possible:")
chosen = activity_selection(meetings)
print("chosen:", chosen, f"({len(chosen)} meetings)")
# The same problem, greedy on the WRONG key.
by_start = []
finish = 0
for name, start, end in sorted(meetings, key=lambda m: m[1]): # by START
if start >= finish:
by_start.append(name)
finish = end
print("greedy by start time instead:", by_start, f"({len(by_start)} meetings)")
Output
How the code works
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.
([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.
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.
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.
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.
Check yourself
0 of 3
Answer without scrolling back up.
Greedy coin change works for [1, 5, 10, 25] but fails for [1, 3, 4]. What does that show?
Familiarity with real currency is why people assume greedy is generally optimal. Nothing about the code changed - only the input.
Activity selection is provably optimal when the meetings are sorted by:
Taking the meeting that frees the room earliest can never shut out a better schedule. Sorted by start time, one long early meeting blocks several short ones.
The practical way to test a greedy idea is to:
The program runs a DP check alongside so the verdict is computed rather than asserted. A counterexample is usually small when it exists at all.
Cheat sheet
Greedy Algorithms
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.
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.