Greedy Algorithms

Learning Objectives

By the end of this page, you should be able to:

• Define the greedy choice property and optimal substructure, and explain why both are needed for greedy correctness.
• Solve activity selection, fractional knapsack, coin change, and Huffman coding using a greedy strategy.
• Distinguish problems where greedy gives the optimal answer from problems where it fails, using coin change as the canonical counterexample.
• Analyze the time complexity of a greedy algorithm, including the cost of sorting or using a priority queue.
• Compare greedy algorithms with dynamic programming and brute force, and justify when each is the right tool.

Quick Answer

A greedy algorithm builds a solution one step at a time, always picking the option that looks best right now, and never revisiting that choice. It works only when a problem has two properties: the greedy choice property (a locally optimal pick is always part of some globally optimal solution) and optimal substructure (an optimal solution to the whole problem contains optimal solutions to its subproblems). When both hold — as in activity selection, Huffman coding, and Kruskal's/Prim's MST algorithms — greedy is fast and simple, usually O(n log n). When they don't hold, as in the 0/1 knapsack or coin change with arbitrary denominations, greedy gives a wrong or suboptimal answer, and you need dynamic programming instead.

Greedy Choice Property and Optimal Substructure

These two properties are what separate "an algorithm that happens to make greedy-looking choices" from "a correct greedy algorithm." Skipping this check is the single biggest reason students misuse greedy on exams.

Greedy choice property: at every step, you can make the choice that looks best at that moment, without knowing the future, and still be guaranteed a globally optimal solution exists that includes this choice. You never need to reconsider it later.

Optimal substructure: if you strip away the piece you just chose, the optimal solution to what remains is itself an optimal solution to the smaller subproblem. This is the same property dynamic programming relies on — the difference is that DP explores all subproblem choices and combines them, while greedy trusts that only one choice (the greedy one) needs to be explored.

A problem needs both properties for greedy to be provably correct. Optimal substructure alone (true for 0/1 knapsack too) is not enough — you also need the greedy choice property, which 0/1 knapsack lacks.

Worked Example 1: Activity Selection

Problem: Given activities with start and end times, select the maximum number that don't overlap.

Greedy strategy: always pick the activity that finishes earliest among the remaining compatible ones. Finishing early leaves the most room for future activities — that's the greedy choice property in action, and it can be proven by an exchange argument (any optimal solution can be modified to include the earliest-finishing activity without making it worse).

def activity_selection(activities):
    # Sort activities by their finish time
    activities.sort(key=lambda x: x[1])
    selected = []
    last_end_time = 0

    for start, end in activities:
        if start >= last_end_time:
            selected.append((start, end))
            last_end_time = end

    return selected

# Example usage:
activities = [(1, 3), (2, 4), (3, 5), (0, 6), (5, 7), (8, 9)]
print(activity_selection(activities))
# [(1, 3), (3, 5), (5, 7), (8, 9)]

Why it matters: this is the textbook proof-friendly greedy problem — it's how interviews and exams test whether you actually understand why greedy works, not just that it does.

Real-world example: a single meeting room and a list of booking requests — the room scheduler picks the next meeting that ends soonest so it can fit in as many meetings as possible. The same logic runs inside CPU job schedulers and conference-room booking systems.

Time complexity: O(n log n) for the sort, O(n) for the single scan — O(n log n) overall.

Worked Example 2: Fractional Knapsack

Problem: given items with a weight and value, and a knapsack with limited capacity, maximize total value. Unlike 0/1 knapsack, you may take a fraction of an item.

Greedy strategy: always take as much as possible of the item with the highest value-to-weight ratio.

class Item:
    def __init__(self, value, weight):
        self.value = value
        self.weight = weight
        self.ratio = value / weight

def fractional_knapsack(items, capacity):
    items.sort(key=lambda x: x.ratio, reverse=True)
    total_value = 0.0
    for item in items:
        if capacity - item.weight >= 0:
            capacity -= item.weight
            total_value += item.value
        else:
            total_value += item.value * (capacity / item.weight)
            break
    return total_value

# Example usage:
items = [Item(60, 10), Item(100, 20), Item(120, 30)]
print(fractional_knapsack(items, 50))  # 240.0

Why it works here but not in 0/1 knapsack: because you can take fractions, there's no "wasted" leftover capacity — the highest-ratio item can always be fully exploited or exactly fill the remaining space. In 0/1 knapsack, an item is all-or-nothing, so a high-ratio item might not fit, forcing you to compare combinations — which breaks the greedy choice property and requires dynamic programming.

Real-world example: a delivery truck with a fixed volume, loading liquid or bulk goods (like grain or oil) where partial loads are possible — load the highest-value-per-liter goods first.

Time complexity: O(n log n) for sorting by ratio.

Worked Example 3: Coin Change — Canonical vs Non-Canonical Systems

This is where greedy's biggest trap shows up.

Canonical coin system (e.g., US coins: 25, 10, 5, 1): the greedy "always take the biggest coin that fits" strategy happens to produce the minimum number of coins.

def coin_change_greedy(coins, amount):
    coins.sort(reverse=True)
    result = []
    for coin in coins:
        while amount >= coin:
            amount -= coin
            result.append(coin)
    return result if amount == 0 else "Cannot make exact change"

print(coin_change_greedy([25, 10, 5, 1], 63))
# [25, 25, 10, 1, 1, 1] -> 6 coins (this IS optimal for US coins)

Non-canonical system: with denominations [1, 3, 4] and target 6, greedy picks 4 + 1 + 1 (3 coins), but the optimal answer is 3 + 3 (2 coins). Greedy fails because taking the largest coin isn't always part of some optimal solution — the greedy choice property does not hold for arbitrary denominations.

print(coin_change_greedy([4, 3, 1], 6))
# [4, 1, 1] -> 3 coins, but [3, 3] -> 2 coins is better!

The correct general-purpose solution is dynamic programming (O(amount × number of denominations)), which checks all combinations instead of trusting one locally "obvious" choice.

Time complexity: O(n) for the greedy version (n = coins used), but it is only correct on canonical systems — complexity is irrelevant if the answer is wrong.

Worked Example 4: Huffman Coding

Problem: build a variable-length prefix code that minimizes the total encoded length of a message, given character frequencies.

Greedy strategy: repeatedly merge the two least-frequent nodes into a new node whose frequency is their sum, until one tree remains. Frequent characters end up near the root (short codes); rare characters end up deep (long codes).

import heapq

class Node:
    def __init__(self, freq, char=None, left=None, right=None):
        self.freq = freq
        self.char = char
        self.left = left
        self.right = right
    def __lt__(self, other):
        return self.freq < other.freq

def huffman(freqs):
    heap = [Node(f, c) for c, f in freqs.items()]
    heapq.heapify(heap)
    while len(heap) > 1:
        a = heapq.heappop(heap)
        b = heapq.heappop(heap)
        heapq.heappush(heap, Node(a.freq + b.freq, left=a, right=b))
    return heap[0]

def codes(node, prefix="", table=None):
    table = table if table is not None else {}
    if node.char is not None:
        table[node.char] = prefix or "0"
    else:
        codes(node.left, prefix + "0", table)
        codes(node.right, prefix + "1", table)
    return table

freqs = {"a": 45, "b": 13, "c": 12, "d": 16, "e": 9, "f": 5}
tree = huffman(freqs)
print(codes(tree))

Why it works: merging the two smallest frequencies first is provably part of an optimal encoding (exchange argument again) — and each merge creates a smaller subproblem with the same structure, giving optimal substructure.

Real-world example: ZIP, GZIP, JPEG, and MP3 all use Huffman coding (or a close variant) as part of their compression pipeline to shrink file sizes losslessly.

Time complexity: O(n log n), where n is the number of distinct symbols — each of the n−1 merges costs O(log n) for the heap operations.

Big-O Summary

Problem	Greedy Strategy	Time Complexity	Always Optimal?
Activity Selection	Pick earliest finish time	O(n log n)	Yes
Fractional Knapsack	Pick highest value/weight ratio	O(n log n)	Yes
Coin Change (canonical)	Pick largest coin ≤ remaining	O(n)	Yes, only for canonical systems
Coin Change (arbitrary)	Pick largest coin ≤ remaining	O(n)	No — needs DP, O(amount × coins)
Huffman Coding	Merge two smallest frequencies	O(n log n)	Yes
Kruskal's MST	Pick smallest edge that avoids a cycle	O(E log E)	Yes

Decision Flow: When Does Greedy Work?

Key Terms

Term	Definition
Greedy choice property	A locally optimal choice at each step is guaranteed to be part of some globally optimal solution.
Optimal substructure	An optimal solution to a problem contains optimal solutions to its subproblems.
Exchange argument	A proof technique showing any optimal solution can be transformed to include the greedy choice without getting worse.
Canonical coin system	A set of denominations for which the greedy "largest coin first" strategy always gives the minimum number of coins.
Fractional knapsack	A knapsack variant where items can be split; solvable optimally by greedy on value-to-weight ratio.
Huffman coding	A greedy algorithm that builds an optimal prefix-free binary code by repeatedly merging the two lowest-frequency nodes.
Activity selection	Choosing the maximum set of non-overlapping intervals by always picking the earliest-finishing option.

Common Mistakes

Misconception	Why It's Wrong	Correct Understanding
"Greedy algorithms always give the optimal solution because they're 'smart' choices."	Greedy only works when the greedy choice property genuinely holds. 0/1 knapsack and arbitrary-denomination coin change both have optimal substructure but not the greedy choice property, so greedy gives wrong answers there.	Before applying greedy, prove (or at least test) that a locally best pick can never block a better global solution — otherwise use dynamic programming.
"Coin change is always solvable optimally with the largest-coin-first approach."	This only holds for canonical denomination systems like standard currency. With coins like [1, 3, 4], greedy on target 6 gives 3 coins (4+1+1) instead of the optimal 2 (3+3).	Check whether the denomination set is canonical; if not, or if you're unsure, use the DP formulation that tries every coin at every amount.
"Greedy and dynamic programming are basically the same thing since both use optimal substructure."	DP explores all valid subproblem choices and combines the best results (often with memoization); greedy commits to one choice per step and never looks back, which is only valid under the greedy choice property.	Greedy is a special, faster case that applies only to a subset of problems that DP can solve — greedy trades DP's exhaustive search for irrevocable speed, and that trade is only safe when justified.

Comparison and Connections

Aspect	Greedy	Dynamic Programming	Brute Force
Choice strategy	Makes one locally optimal choice per step, never revisits	Explores overlapping subproblems, combines optimal results	Explores all possible solutions exhaustively
Requires	Greedy choice property + optimal substructure	Optimal substructure + overlapping subproblems	No structural assumptions
Typical complexity	O(n log n) or O(n)	Polynomial but higher (e.g., O(n × capacity))	Exponential, e.g. O(2ⁿ)
Correctness guarantee	Only when properties are proven to hold	Always optimal if recurrence is correct	Always optimal (by definition)
Example	Activity selection, Huffman coding, Kruskal's MST	0/1 knapsack, longest common subsequence, arbitrary coin change	Traveling salesman (small n), subset generation

Practice Questions

Recall

1. What are the two properties a problem must have for a greedy algorithm to be provably correct? Answer guidance: greedy choice property (a local best choice is part of some global optimum) and optimal substructure (optimal solutions are built from optimal sub-solutions).

2. In Huffman coding, which two nodes are merged at each step? Answer guidance: the two nodes with the lowest frequency currently in the priority queue/heap.

Understanding

3. Explain why the fractional knapsack problem can be solved greedily but the 0/1 knapsack problem cannot. Answer guidance: fractions let you always fully exploit the best ratio item or exactly fill remaining capacity with no waste; 0/1's all-or-nothing constraint means a high-ratio item might not fit, requiring comparison of combinations — which greedy can't do.

4. Why does sorting by finish time (not start time or duration) work for activity selection? Answer guidance: finishing earliest leaves the maximum remaining time window for future activities, which can be proven via an exchange argument to never be worse than any other choice.

Application

5. You have coins [1, 3, 4] and need to make 6 cents. Trace both the greedy algorithm and the optimal answer. Answer guidance: greedy gives 4+1+1 = 3 coins; optimal is 3+3 = 2 coins — this demonstrates a non-canonical system.

6. A conference has 6 talks with overlapping time slots. Describe, step by step, how you'd pick the maximum non-conflicting subset. Answer guidance: sort by end time, iterate, and pick a talk whenever its start time is ≥ the end time of the last picked talk (mirrors the activity_selection code above).

Analysis

7. Compare how greedy and dynamic programming would each approach the coin change problem with denominations [1, 3, 4] and amount 6. Which is guaranteed correct, and why? Answer guidance: DP is guaranteed correct because it checks min(dp[amount - coin] + 1) over all coins for every sub-amount, effectively testing every combination; greedy is not guaranteed because it commits to the largest coin without checking if that blocks a better combination.

8. A friend says "greedy is just a faster, simpler version of DP, so I'll always try greedy first." Evaluate this strategy for exam problem-solving. Answer guidance: reasonable as a first instinct for speed, but risky without verifying the greedy choice property — a stronger exam strategy is to look for a counterexample (like non-canonical coins) before committing to greedy, since one counterexample disproves it.

FAQ

Q: Is greedy always faster than dynamic programming? A: Usually yes when applicable — greedy avoids the extra bookkeeping (tables, memoization) that DP needs — but "faster" is irrelevant if greedy gives the wrong answer. Correctness comes first.

Q: How do I prove a greedy algorithm is correct on an exam? A: The standard technique is an exchange argument: assume an optimal solution that doesn't include the greedy choice, then show you can swap in the greedy choice without making the solution worse, contradicting the assumption that greedy's choice is never optimal.

Q: Why does the 0/1 knapsack problem need DP instead of greedy? A: Because items can't be split, the highest-ratio item might not fit the remaining capacity, forcing you to compare entire combinations of items rather than committing to one at a time — greedy has no way to "undo" a bad early pick.

Q: Are Kruskal's and Prim's algorithms greedy? A: Yes. Kruskal's repeatedly picks the smallest edge that doesn't create a cycle; Prim's repeatedly picks the smallest edge that extends the current tree. Both rely on the cut property of minimum spanning trees, which is their version of the greedy choice property.

Q: What's a quick way to test if greedy will work before writing full code? A: Try to find a small counterexample by hand — 3 to 5 items or a handful of coin denominations. If greedy's answer matches brute force on several small cases, that's a decent (not proof-level) sanity check; for exams, still explain the exchange argument.

Q: Does greedy ever combine with dynamic programming? A: Yes — some problems use a greedy step to reduce the search space and then DP for the remaining decisions, and some DP solutions are later "optimized" into a greedy form once the greedy choice property is proven for that specific case (job sequencing with deadlines is a common example).

Quick Revision

• Greedy makes the locally best choice at each step and never reconsiders it.
• Requires two properties: greedy choice property + optimal substructure.
• Activity selection: sort by finish time, pick compatible earliest-finishing activities — O(n log n), always optimal.
• Fractional knapsack: sort by value/weight ratio, take greedily — O(n log n), always optimal.
• Coin change greedy works only on canonical systems (e.g., US coins); fails on sets like [1, 3, 4].
• 0/1 knapsack and arbitrary coin change need dynamic programming, not greedy.
• Huffman coding: merge two lowest-frequency nodes repeatedly using a min-heap — O(n log n).
• Kruskal's and Prim's MST algorithms are greedy, relying on the cut property.
• Exchange argument is the standard proof technique for greedy correctness.
• Greedy is faster than DP (often O(n log n) vs polynomial-higher) but only when provably correct.
• Always test small counterexamples before trusting a greedy strategy on an exam.

Related Topics

Prerequisites: Big-O notation and algorithm analysis, sorting algorithms, basic recursion, priority queues/heaps.

Related Topics: Dynamic Programming, Divide and Conquer, Graph Algorithms (Minimum Spanning Trees — Kruskal's and Prim's), Data Compression.

Next Topics: Dynamic Programming (for problems where greedy fails), Graph Algorithms (Dijkstra's shortest path, which is greedy with a correctness caveat on negative weights), NP-Completeness (why some optimization problems resist both greedy and DP).