Greedy Algorithms: How They Work and When They Fail

What a greedy algorithm is

A greedy algorithm solves a problem in steps. At each step it picks the option that looks best right now and never goes back to change that decision.

It gives the optimal answer only when two conditions hold:

• Greedy choice property — some optimal solution starts with the locally best choice, so taking it never closes the door to the best result.
• Optimal substructure — after that choice, what remains is a smaller instance of the same problem, and solving it optimally completes an optimal answer.

When both hold, greedy algorithms are simple and fast, usually dominated by a sort: O(n log n). When they do not, a greedy algorithm still returns an answer — just not the best one, and nothing warns you.

Coin change: works for some coin sets only

Task: pay an amount with the fewest coins. Greedy rule: always take the largest coin that fits.

def greedy_coins(amount, coins):
    result = []
    for c in sorted(coins, reverse=True):
        while amount >= c:
            amount -= c
            result.append(c)
    return result

With coins 1, 5, 10, 25 and amount 30 you get 25 + 5 — optimal. Coin systems where greedy is always optimal are called canonical, and many real currencies are designed that way.

Now take coins 1, 3, 4 and amount 6:

• Greedy: 4 + 1 + 1 — three coins.
• Optimal: 3 + 3 — two coins.

The first "best" choice (4) made the rest worse. For arbitrary coin sets you need dynamic programming: compute the minimum number of coins for every amount from 0 up to the target.

def min_coins(amount, coins):
    INF = float("inf")
    dp = [0] + [INF] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and dp[a - c] + 1 < dp[a]:
                dp[a] = dp[a - c] + 1
    return dp[amount] if dp[amount] != INF else -1

Interval scheduling: sort by end time

Task: choose the maximum number of non-overlapping meetings for one room.

The correct greedy rule is pick the meeting that finishes earliest, then repeat with the meetings that start after it ends.

def max_meetings(intervals):
    count, last_end = 0, float("-inf")
    for start, end in sorted(intervals, key=lambda x: x[1]):
        if start >= last_end:
            count += 1
            last_end = end
    return count

Why it works: finishing earliest leaves the most room for the rest. "Shortest first" or "earliest start first" look reasonable but fail on simple examples. If meetings have weights (some are more valuable), greedy no longer works and you need DP over sorted intervals.

Huffman coding: merge the two rarest

Huffman coding builds an optimal prefix code for compression: frequent symbols get short codes, rare ones get long codes.

1. Put every symbol in a priority queue with its frequency.
2. Remove the two least frequent nodes and merge them into a new node whose frequency is their sum.
3. Push it back and repeat until one tree remains.
4. Read codes from the root: left edge is 0, right edge is 1.

The greedy choice — merging the two rarest symbols — is provably safe: in some optimal tree they are siblings at the deepest level. Huffman coding is part of formats such as DEFLATE, used in ZIP and PNG.

When greedy fails and DP is needed

The 0/1 knapsack is the classic trap. Capacity 50, items (weight, value): (10, 60), (20, 100), (30, 120). Greedy by value per kilo takes the first two for a value of 160. The best answer is the second and third items for 220. With fractional knapsack, where you can take part of an item, the same greedy rule is optimal.

How to check a greedy idea

• Search for a small counterexample. Try tiny inputs by hand or compare against brute force in a quick test.
• Try an exchange argument. Take any optimal solution and show you can swap its first choice for the greedy one without making it worse.
• Watch for weights and "all or nothing" items. They often break greedy rules.
• If in doubt, write the DP first, then see whether it simplifies to a greedy rule.