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.
Quick Context
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 must hold:
Greedy choice property — a globally optimal solution can be reached by making locally optimal choices. You never need to sacrifice now for later.
Optimal substructure — after making that choice, what remains is a smaller instance of the same problem.
Proving the first usually needs an exchange argument: show that any optimal solution can be modified to include the greedy choice without getting worse.
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.
Interactive Exploration Guide
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.
Key Takeaway
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.
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.