Greedy Algorithms
A greedy algorithm takes the best-looking option at every step and never reconsiders. That makes it fast and simple — and wrong on many problems. The real work is proving the local choice cannot damage the global answer.
Commit and Never Look Back
A greedy algorithm builds a solution by repeatedly taking whatever looks best right now, and never reconsidering that choice. There is no backtracking and no comparison of alternatives — each decision is made once and stands.
That makes greedy algorithms fast and short. Where dynamic programming explores every option and keeps the best, greedy makes one choice per step, so the cost is usually the sorting that establishes the order plus a single pass — O(n log n) dominated by the sort.
It also makes them frequently wrong. Taking the locally best option can foreclose a better global solution, and the failure is silent: the algorithm returns a plausible answer with no indication it is suboptimal. This is the essential difficulty of the topic. Greedy is not a technique you apply and verify afterwards; it is one you must justify before trusting.
The making-change example shows both sides. With coins of 1, 5, 10 and 25, taking the largest coin that fits repeatedly gives the fewest coins for any amount — greedy works. With coins of 1, 3 and 4, making 6 greedily takes 4 then 1 then 1, three coins, when 3 + 3 is two. Same algorithm, same shape of problem, different coin set, and it breaks.
So the question is never 'is greedy fast' but 'is greedy correct for this problem' — and the two properties in the next section are how that is answered.
- One choice per step, never revisited — no backtracking
- Usually O(n log n), dominated by an initial sort
- Wrong on many problems, and wrong silently
- Coin change works for 1/5/10/25 and fails for 1/3/4
The Two Properties, and How to Prove Them
A greedy algorithm is correct when the problem has both of the following. Stating them is the standard way to justify a greedy solution.
The greedy choice property: a globally optimal solution can be reached by making the locally optimal choice at each step. Formally, there exists an optimal solution that contains the greedy first choice — so committing to it never rules out optimality.
Optimal substructure: after making that choice, the remaining problem is a smaller instance of the same problem, and combining the greedy choice with an optimal solution to the remainder gives an optimal whole. This is the same property dynamic programming requires; greedy differs by needing only one subproblem rather than all of them.
The standard proof technique is the exchange argument, and it is worth knowing as a template. Assume some optimal solution O differs from the greedy solution G. Find the first place they diverge. Show that O can be modified to agree with G's choice there without becoming worse — usually by swapping G's choice in and the conflicting element out. Repeating the exchange transforms O into G while preserving optimality, so G is optimal too.
For activity selection, the exchange is concrete: if the optimal schedule starts with some activity other than the earliest-finishing one, replacing it with the earliest-finishing activity cannot conflict with anything later, so the modified schedule is still valid and just as large.
The other, faster route is finding a counterexample. Since greedy fails often, actively trying to break a candidate strategy is efficient use of time. Construct small adversarial cases: a slightly-too-large item that blocks two good ones, a locally attractive option that closes off a much better path. If a counterexample exists, the problem is usually dynamic programming instead.
The practical habit for an exam or interview: state the greedy choice, then either sketch the exchange argument or produce a counterexample. An unjustified greedy claim is the weakest possible answer even when it happens to be right.
- Greedy choice property: some optimal solution contains the greedy choice
- Optimal substructure: the remainder is a smaller instance of the problem
- Exchange argument: modify an optimal solution toward greedy without loss
- Failing that, hunt for a counterexample — greedy fails often
Sorting by the Right Key
In most greedy problems the algorithm is trivial once the ordering is chosen, so the real work is deciding what to sort by. Getting the key right is the insight; the rest is a loop.
Activity selection — choose the most non-overlapping activities from a set with start and end times. Sort by finish time and repeatedly take the earliest-finishing activity compatible with what is already chosen. Finishing earliest leaves the most remaining time, and that is the exchange argument in one sentence.
The tempting alternatives both fail, which is instructive. Sorting by start time takes an activity that begins early and runs long, blocking several. Sorting by duration takes a short activity positioned to overlap two others that could both have been taken. Only finish time works, and only the exchange argument explains why.
Fractional knapsack — fill a capacity with items, taking fractions if desired, maximising value. Sort by value per unit weight and take greedily, splitting the last item to fill exactly. Because items divide, there is never a reason to prefer a lower ratio.
0/1 knapsack — the same problem where items must be taken whole — is not greedy. The ratio order can be wrong: a high-ratio item may consume capacity that two lower-ratio items would have used better. The indivisibility breaks the exchange argument, and the problem requires dynamic programming. This contrast is the single most useful illustration of where the boundary lies.
Interval scheduling to minimise rooms sorts by start time and uses a min-heap of end times. Job sequencing with deadlines sorts by profit descending and places each job as late as its deadline permits. Huffman coding repeatedly merges the two least frequent symbols, which is greedy on a priority queue rather than on a sorted list.
Dijkstra's algorithm and Prim's and Kruskal's for minimum spanning trees are all greedy, and their correctness rests on the same kind of argument — Kruskal's on the cut property, which states that the lightest edge crossing any partition of the vertices belongs to some minimum spanning tree.
| Problem | Sort by | Greedy? |
|---|---|---|
| Activity selection | Finish time | Yes |
| Fractional knapsack | Value ÷ weight | Yes |
| 0/1 knapsack | — | No — use DP |
| Minimum rooms | Start time, heap of ends | Yes |
| Job sequencing | Profit descending | Yes |
| Huffman coding | Frequency, via a heap | Yes |
| Coin change | Largest coin first | Only for some coin sets |
- Activity selection sorts by finish time — start time and duration both fail
- Fractional knapsack sorts by value density and splits the last item
- 0/1 knapsack is not greedy; indivisibility breaks the argument
- Dijkstra, Prim and Kruskal are greedy with proofs behind them
Terms, operations, and practical uses
Core vocabulary
- Greedy ChoiceMaking the choice that looks best at the current moment without considering the long-term consequences.
- Local OptimumThe best possible choice at a specific step in the algorithm.
- Global OptimumThe absolute best possible solution for the entire problem.
Characteristics
- IrrevocableGreedy algorithms typically never undo or reconsider a choice once it is made (no backtracking).
- Proof of CorrectnessA mathematical proof is usually required to show that local greedy choices indeed lead to the global optimal solution.
- Sorting PrerequisiteMost greedy algorithms require sorting the input data first, making their time complexity bounded by O(N log N).
Classic problems
- Activity SelectionChoosing the maximum number of non-overlapping intervals (activities) by sorting by end time.
- Huffman CodingCreating an optimal prefix code for data compression by repeatedly merging the least frequent items.
- Fractional KnapsackUnlike 0/1 Knapsack, taking fractions of items allows a greedy approach based on value/weight ratio.
Make change for 40 cents using US coins
def make_change(amount, coins):
count = 0
for coin in coins:
while amount >= coin:
amount -= coin
count += 1
return count
print(make_change(40, [25, 10, 5, 1]), 'coins (25, 10, 5)')#include <iostream>
#include <vector>
using namespace std;
int makeChange(int amount, vector<int>& coins) {
int count = 0;
for (int coin : coins) { // coins must be sorted largest first
while (amount >= coin) {
amount -= coin;
count++;
}
}
return count;
}
int main() {
vector<int> coins = {25, 10, 5, 1};
cout << makeChange(40, coins) << " coins (25, 10, 5)\n";
}class Main {
static int makeChange(int amount, int[] coins) {
int count = 0;
for (int coin : coins) { // coins must be sorted largest first
while (amount >= coin) {
amount -= coin;
count++;
}
}
return count;
}
public static void main(String[] args) {
int[] coins = {25, 10, 5, 1};
System.out.println(makeChange(40, coins) + " coins (25, 10, 5)");
}
}Step through it
Running on amount = 40, coins = [25, 10, 5, 1]
Read all 9 Steps
- Sort coins largest first Amount is 40¢ and the coin set is [25, 10, 5, 1]. Greedy requires descending order: the whole strategy is 'take the biggest coin that still fits', which is meaningless on an unsorted list.
- Take 25 — remaining 15 40 ≥ 25, so take one quarter. The amount drops to 15 and the count rises to 1. Greedy commits immediately and never revisits this choice.
- 25 no longer fits, move on 15 < 25, so the quarter is exhausted. The pointer advances to the dime permanently — a coin denomination is never reconsidered once passed.
- Take 10 — remaining 5 15 ≥ 10, so take one dime. The amount drops to 5 and the count rises to 2.
- 10 no longer fits, move on 5 < 10, so advance to the nickel. Each denomination is visited exactly once, which is why the loop runs in O(number of denominations) rather than O(amount).
- Take 5 — remaining 0 5 ≥ 5, so take one nickel. The amount reaches exactly 0 and the count rises to 3. The pennies are never needed.
- Amount is 0, stop With nothing left to make, the loop exits before touching the penny. Three coins — 25 + 10 + 5 — is genuinely the minimum for this coin set.
- Why this worked: the exchange argument Greedy is only provably optimal when taking the largest coin never forces a worse remainder. For US denominations each coin divides into the next, so any solution using smaller coins can be swapped upward without increasing the count.
- Where greedy breaks Change the coin set to [25, 20, 1] and ask for 40. Greedy takes 25, then must pay 15 in pennies — 16 coins. The optimal answer is two 20s. Same algorithm, different denominations, wrong result: greedy needs proof, not intuition.
When It Fails, and What to Use Instead
Recognising failure is as valuable as recognising success, and the failure modes are consistent.
Indivisible items with a capacity. 0/1 knapsack is the archetype. Whenever a choice is all-or-nothing and consumes a shared budget, the greedy order can strand capacity that a different combination would have used. Dynamic programming over remaining capacity is the fix.
Choices that constrain the future non-locally. In coin change with arbitrary denominations, taking the largest coin can leave a remainder requiring many small coins. Greedy sees only the current step; DP evaluates every first coin and takes the best outcome.
Problems requiring a global view. The longest path in a graph cannot be built greedily — a locally attractive edge can lead into a dead end, and the problem is NP-hard in general. Travelling salesman likewise: nearest-neighbour is a reasonable heuristic and is not optimal.
When greedy fails, the escalation ladder is usually dynamic programming first, since it evaluates all choices while reusing overlapping subproblems. If subproblems do not overlap, backtracking with pruning enumerates the possibilities while cutting hopeless branches.
The contrast in one line: greedy takes one option and moves on; DP takes every option and keeps the best. Greedy is faster and needs a proof; DP is slower and needs only the two structural properties.
It is worth adding that a failing greedy algorithm is often still useful as an approximation. Nearest-neighbour for TSP, greedy set cover, and greedy bin packing all give solutions with provable bounds relative to optimal — greedy set cover is within a factor of ln n, and first-fit-decreasing bin packing within about 22% of optimal. When the exact problem is intractable, a greedy algorithm with a known approximation ratio is frequently the right engineering answer.
The summary to carry into a problem: try greedy first, because it is quick to test. Then either prove it or break it. Do not ship it on intuition alone.
- Indivisible items with a shared budget break greedy — use DP
- Longest path and TSP need a global view greedy cannot provide
- Greedy picks one option; DP evaluates all and keeps the best
- A failing greedy is often still a bounded approximation worth using