Greedy Algorithms: When They Work and When They Mislead

Version note: The code in this post was built with .NET 10 and C# 14 and verified with xUnit v3 4.0.2 tests.

Guess First

Picture code that gives change at the till. The first algorithm that comes to mind is what cashiers do: start with the largest coin, give as many as fit, then move to the next smaller one.

// Largest coin first. Optimal only for "canonical" coin systems.
public static List<int> GreedyChange(int[] coins, int amount)
{
    List<int> used = [];
    foreach (int coin in coins.OrderDescending())
    {
        while (amount >= coin)
        {
            amount -= coin;
            used.Add(coin);
        }
    }

    return amount == 0 ? used : [];
}

With Turkish lira coins (1, 5, 10, 25, 50 kuruş and 1 lira), does this algorithm always give the fewest coins? And if your only coins were 1, 3 and 4 units and you had to give 6 units of change, how many coins would it give, and would that be the fewest?

What Greedy Is and When It Is Correct

A greedy algorithm makes the choice that looks best at each step and never goes back. It is the exact opposite of the backtracking in the 19th post of the series: there we tried every branch and pruned the hopeless ones, here we pick a single branch at each step and never open the others. That is why greedy algorithms are usually very fast, often a sort plus a single pass: O(n log n).

Speed does not come for free. For greedy to give the right answer the problem needs two properties. The greedy choice property: there is always an optimal solution that contains the choice that looks best right now. Optimal substructure: after making that choice, what remains is a smaller problem of the same kind, and its optimal solution is part of the optimal solution of the whole. We will see the second one for dynamic programming in the 21st post of the series too; the first one is what sets greedy apart.

The classic way to show the greedy choice property is the exchange argument: take an optimal solution, swap in the choice greedy made, and show the result does not get worse. Let's do that on an example.

Interval Scheduling: The Most Meetings in One Room

The Bookstore office has a single meeting room and the following meetings have been requested for the day. What is the largest number of meetings that can be held without overlap?

public sealed record Meeting(string Title, int Start, int End);

// Activity selection: always take the meeting that ends first. O(n log n).
public static List<Meeting> MaxNonOverlapping(IEnumerable<Meeting> meetings)
{
    List<Meeting> chosen = [];
    int freeAt = int.MinValue;
    foreach (Meeting m in meetings.OrderBy(m => m.End))
    {
        if (m.Start >= freeAt)
        {
            chosen.Add(m);
            freeAt = m.End;
        }
    }

    return chosen;
}

Meeting[] day =
[
    new("Standup", 9, 10), new("Pricing", 9, 12), new("Catalog", 10, 11),
    new("Review", 11, 13), new("Lunch talk", 12, 13), new("Retro", 13, 14),
];

one room: Standup 9-10, Catalog 10-11, Review 11-13, Retro 13-14

The rule is "take the meeting that ends first". Let's see why it is correct with an exchange argument. Take an optimal schedule and call its first meeting X. The meeting greedy picks, G, ends earliest among all meetings, so G cannot end later than X. Remove X from the schedule and put G in its place: since G ends no later than X, it does not overlap any meeting after X, and the number of meetings stays the same. So there is always an optimal schedule that starts with G. The rest is the same problem on meetings that start after G ends; by induction greedy is optimal.

Other intuitive rules fail this test. Let's try "take the shortest meeting" on a three-meeting day:

// Wrong greedy: pick the shortest meeting first.
Meeting[] trap = [new("A", 9, 12), new("B", 11, 13), new("C", 12, 15)];
List<Meeting> shortestFirst = [];
foreach (Meeting m in trap.OrderBy(m => m.End - m.Start))
{
    if (shortestFirst.All(x => m.End <= x.Start || m.Start >= x.End)) shortestFirst.Add(m);
}

shortest first: B; earliest end: A, C

The shortest meeting B (2 hours) overlaps both others; picking it destroys the chance of holding A and C together. Counterexamples exist for "take the earliest start" or "take the one with the fewest conflicts" too. In greedy the selection rule is everything, and intuition is not proof.

Number of Meeting Rooms: With a Min-Heap

The question changes: how many rooms do we need at least to hold all meetings? This time we sort meetings by start time and keep the end times of occupied rooms in a min-heap (the 13th post of the series). When a new meeting starts, if the room that frees up earliest is already free we use it; otherwise we open a new room:

// Minimum rooms: sort by start, keep a min-heap of end times of rooms in use.
public static int MinRooms(IEnumerable<Meeting> meetings)
{
    PriorityQueue<Meeting, int> busyUntil = new();
    int rooms = 0;
    foreach (Meeting m in meetings.OrderBy(m => m.Start))
    {
        if (busyUntil.TryPeek(out _, out int earliestEnd) && earliestEnd <= m.Start)
        {
            busyUntil.Dequeue(); // that room is free again: reuse it
        }

        busyUntil.Enqueue(m, m.End);
        rooms = Math.Max(rooms, busyUntil.Count);
    }

    return rooms;
}

rooms needed for all: 2

The heap's size at any moment is the number of meetings running at the same time; the largest value it reaches during the day is the number of rooms needed. Between 9 and 10 Standup and Pricing run together, between 12 and 13 Review and Lunch talk; at no moment do three meetings overlap. The cost is O(n log n) for sorting and O(log n) for one heap operation per meeting.

A Brief Look at Huffman Coding

One of the most elegant examples of greedy is the compression code David Huffman published in 1952. The idea: give short bit sequences to frequent characters and long ones to rare characters, and let no code be the beginning (prefix) of another code, so decoding needs no separator. The greedy step: always merge the two lightest trees.

private sealed record Node(char? Symbol, int Weight, Node? Left = null, Node? Right = null);

// Greedy: always merge the two lightest trees. Returns a prefix-free code table.
public static Dictionary<char, string> BuildCodes(string text)
{
    PriorityQueue<Node, (int Weight, int Order)> queue = new();
    int order = 0;
    foreach (IGrouping<char, char> g in text.GroupBy(c => c).OrderBy(g => g.Key))
    {
        queue.Enqueue(new Node(g.Key, g.Count()), (g.Count(), order++));
    }

    while (queue.Count > 1)
    {
        Node a = queue.Dequeue();
        Node b = queue.Dequeue();
        Node parent = new(null, a.Weight + b.Weight, a, b);
        queue.Enqueue(parent, (parent.Weight, order++));
    }

    Dictionary<char, string> codes = [];
    Walk(queue.Dequeue(), "");
    return codes;

    void Walk(Node node, string prefix)
    {
        if (node.Symbol is char c)
        {
            codes[c] = prefix.Length > 0 ? prefix : "0";
            return;
        }

        Walk(node.Left!, prefix + "0");
        Walk(node.Right!, prefix + "1");
    }
}

'o' x5 -> 11
'b' x2 -> 010
'k' x2 -> 011
'r' x1 -> 000
's' x2 -> 100
't' x1 -> 001
' ' x1 -> 1010
'e' x1 -> 1011
bits: Huffman=42, 8-bit=120

In the text "bookstore books" the most frequent character "o" is encoded in 2 bits and the rare ones in 3-4 bits; 42 bits in total, against 120 bits for an 8-bit-per-character encoding. We added a sequence number to the priority because of the FIFO (First-In-First-Out) trap from the 13th post of the series: if it is undefined which tree comes out first on equal weights, the code table can change from run to run. Huffman still lives on today as part of formats like DEFLATE (the compression format used by zip and gzip).

Where Greedy Goes Wrong: Coins

Back to the opening question. 6 units with 1, 3 and 4 unit coins:

{1,3,4} amount 6: greedy=[4, 1, 1] optimal coins=2

Greedy takes 4 first and gives two 1s for the remaining 2: three coins. Yet 3 + 3 does the same job with two. The exchange argument collapses here: there is no optimal solution that contains the "take the largest coin" choice. To find the optimum we need a method that computes the best answer for every sub-amount:

// Exhaustive minimum for small amounts, used to look for counterexamples.
public static int OptimalCoinCount(int[] coins, int amount)
{
    int[] best = new int[amount + 1];
    Array.Fill(best, int.MaxValue);
    best[0] = 0;
    for (int a = 1; a <= amount; a++)
        foreach (int c in coins)
            if (c <= a && best[a - c] != int.MaxValue)
                best[a] = Math.Min(best[a], best[a - c] + 1);
    return best[amount];
}

This small table is dynamic programming itself; we will see how it works in detail in the next post. Here we use it as a referee.

Searching for a Counterexample

If you cannot prove a greedy solution correct, at least search for its failure systematically. Comparing greedy against a small exact solver (or brute force) for every input in a range is far more reliable than intuition:

public static int? FindCounterexample(int[] coins, int maxAmount)
{
    for (int amount = 1; amount <= maxAmount; amount++)
    {
        List<int> greedy = GreedyChange(coins, amount);
        int optimal = OptimalCoinCount(coins, amount);
        if (optimal != int.MaxValue && (greedy.Count == 0 || greedy.Count > optimal))
        {
            return amount;
        }
    }

    return null;
}

{1,5,10,25,50,100}: no counterexample up to 1000
{1,2,5,10,20,50}: no counterexample up to 1000
{1,3,4}: fails at 6: greedy 3 coins, optimal 2
{1,15,25}: fails at 30: greedy 6 coins, optimal 2
{1,7,10}: fails at 14: greedy 5 coins, optimal 2

The Turkish lira kuruş system (1, 5, 10, 25, 50, 100) and the 1, 2, 5, 10, 20, 50 system never fail up to 1,000. Such systems are called canonical, and the cashier's greedy algorithm is optimal for them. In the {1, 15, 25} system, for 30 units greedy gives 25 + 1 + 1 + 1 + 1 + 1 (six coins) while 15 + 15 is two coins. The real-world equivalent is choosing values carelessly when designing a "discount coupon" or "points" system for a campaign: if the checkout software works greedily, customers spend extra coupons without noticing.

The tests pin down both correct and incorrect cases; for the system where no counterexample is found we expect null:

[Theory]
[InlineData(new[] { 1, 5, 10, 25, 50 }, null)]
[InlineData(new[] { 1, 3, 4 }, 6)]
[InlineData(new[] { 1, 15, 25 }, 30)]
public void FindCounterexample_FindsSmallestFailingAmount(int[] coins, int? expected) =>
    Assert.Equal(expected, Greedy.FindCounterexample(coins, 200));

Test run summary: Passed!
  total: 8
  failed: 0
  succeeded: 8
  skipped: 0
  duration: 445ms

"No counterexample up to 1,000" is not a proof. There are polynomial-time tests that decide exactly whether a coin system is canonical, but in practice comparing against an exact solver over a limited range catches most wrong systems immediately: counterexamples usually show up at small amounts.

Production Notes

If you pick greedy for its speed, test its correctness against a referee. For every greedy decision that goes to production (packing shipments, applying coupons, prioritizing campaigns), write a test that compares it on small inputs with brute force or dynamic programming. The test's job is not to prove greedy optimal, but to make the cases where it is not optimal a conscious decision.

Sometimes an approximate answer is enough. For problems like packing books into boxes (bin packing) the exact solution is very expensive; greedy rules like "start with the largest, put it in the first box it fits" (first-fit decreasing) are at most a bounded factor worse than the exact optimum and run in milliseconds. In that case the decision is not "is greedy correct?" but "is this deviation acceptable for the business?", and it should be made by measuring.

Document and name the selection rule. The OrderBy(m => m.End) line is the heart of the algorithm; if someone "simplifies" it to OrderBy(m => m.Start), the code compiles, most tests pass and the result silently gets worse. Comment on why the rule is what it is, and keep a test that breaks the rule, like the trap example, permanently.

Common Pitfalls

Shipping a greedy solution that "seems to work" without searching for a counterexample. The cashier algorithm works flawlessly with lira; the same code makes you spend 6 coupons for 30 units with differently valued coupons. Lucky example data in the tests does not show the algorithm is correct.

Sorting by the wrong criterion. In activity selection, shortest, earliest start or fewest conflicts all look reasonable; only earliest end is correct. The sort criterion should be chosen with a proof, or at least a referee test.

Leaving ties undefined. In Huffman and in every greedy that uses a heap, if the order of equal-priority elements is undefined, the output can change from run to run. The result may still be optimal, but tests and caches expect deterministic output.

Expecting greedy to back out. Greedy never undoes a decision; if it hits a dead end (in the coin example, with no 1-unit coin and a remainder that cannot be given), it finds no solution, even when one exists. That is why GreedyChange returns an empty list; for 6 with {3, 4}, greedy takes 4 and gets stuck at 2, while 3 + 3 is possible. We pinned this case down with a test too:

[Fact]
public void GreedyChange_NoOneCoin_GetsStuck()
{
    Assert.Empty(Greedy.GreedyChange([3, 4], 6));
    Assert.Equal(2, Greedy.OptimalCoinCount([3, 4], 6));
}

A Small Experiment

★☆☆ Change MinRooms to also return which room each meeting is assigned to (keep the room number in the heap). Print the room plan for the Bookstore meeting day.

★★☆ Write your own referee test for activity selection: generate 1,000 random days with 10 meetings each, find the maximum number of meetings for each day with brute force that tries all subsets (Subsets from the 19th post of the series), and compare with greedy. Then change the rule to "shortest first" and count on how many days the test breaks.

★★★ Using FindCounterexample, scan all three-coin systems (1, a, b; a < b ≤ 30) and list which ones are canonical up to 200. Do you see a relationship between b and a in the canonical ones?

The coin example showed greedy's limit: in some problems you cannot make the right choice without knowing the best answer to every subproblem. In the next post we move to the technique that does exactly that: dynamic programming. We start from the exponential version of Fibonacci and bring the same computation down to linear time with memoization and tabulation.