Greedy algorithms

intermediateCommon atGoogleAmazonMetaStripeRead firstSorting and comparatorsIntervalsPractise in the Sandbox →

A greedy algorithm builds the answer one irrevocable choice at a time, always taking what looks best right now. It’s usually a sort plus one pass, O(n log n). It is only correct when the problem has the greedy-choice property, which you justify with an exchange argument: any optimal answer can be changed to include the greedy choice without getting worse.

The idea in plain words

You’re at a conference with overlapping talks and want to attend as many as possible. A natural rule: always pick the talk that ends first, then the next one that ends first among those that start after it, and so on. You never reconsider.

That works. Other rules that sound just as natural don’t:

• Earliest start can lock you into one long talk that blocks five short ones.
• Shortest first can pick a short talk that sits across two others that would have fit.

So greedy is two things at once: an algorithm (sort by some key, take what fits) and a claim that the key is right. The algorithm is easy. The claim is the interview.

The exchange argument

The standard way to prove a greedy rule:

1. Take any optimal solution OPT.
2. Look at the first place where it differs from greedy’s choice g.
3. Show you can swap OPT’s choice there for g and the result is still valid and no worse.
4. Repeat: OPT turns into greedy’s answer one swap at a time, never losing value. So greedy is optimal.

For “earliest finish”: let a be the talk in OPT that ends first. Greedy’s pick g ends no later than a. Replace a with g: everything after a in OPT started after a ended, so it also starts after g ends. Still valid, same count.

See it

Try the three rules on the classic CLRS activity set. Then switch to coin change and pick the 1, 3, 4 preset: grabbing the biggest coin first gives 4 + 1 + 1 when 3 + 3 is better.

When greedy works, and when it doesn't

step through

Activity selectionCoin change

intervals [s, e)

ruleearliest finish

picked0

just takentakenclashes: skippedskipped earlier

Greedy rule: consider intervals by earliest finish, take each one that doesn't clash with what's already taken. Never undo a choice.

↺◀▶ Play▶1 / 13

When to reach for it

The problem says…	Why greedy might fit
“maximum number of non-overlapping…”, “fewest to remove so none overlap”	Earliest finish is provably optimal.
“minimum number of points / arrows / stations to cover all…”	Place each one as late as possible (at the earliest end).
“schedule to minimise total waiting / lateness”	Sort by processing time (shortest first) or by deadline. Each has an exchange proof.
“fewest jumps / refuels / platforms”	Often greedy on “farthest reachable”.
“minimum spanning tree”, “Huffman code”, “Dijkstra”	Famous greedy algorithms with known proofs. See MST and shortest paths.
“maximum value”, “fewest coins” with arbitrary numbers	Warning sign. Usually DP or knapsack, unless you can prove otherwise.

How it works

1. Decide what “best right now” means: a sort key or a priority (often via a heap if it changes as you go).
2. Process candidates in that order.
3. For each one, take it if it keeps the solution valid; otherwise skip it. Never undo.
4. Before coding, convince yourself with an exchange argument, then try to break it with a small counterexample.

Activity selection, the textbook greedy (CLRS §16.1): sort by finish time, take whatever starts after the last chosen end.

Python

max_non_overlapping.py

Interval = tuple[int, int]


def max_non_overlapping(intervals: list[Interval]) -> list[Interval]:
    """Largest set of pairwise non-overlapping half-open [s, e) intervals."""
    chosen: list[Interval] = []
    last_end = float("-inf")
    for s, e in sorted(intervals, key=lambda iv: iv[1]):  # 1. earliest finish first
        if s >= last_end:                                  # 2. compatible with everything chosen
            chosen.append((s, e))                          # 3. commit, never undo
            last_end = e
    return chosen


if __name__ == "__main__":
    # The classic CLRS activity set (16.1): the optimum has 4 activities.
    acts = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9),
            (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]
    assert max_non_overlapping(acts) == [(1, 4), (5, 7), (8, 11), (12, 16)]
    assert max_non_overlapping([(1, 3), (3, 5)]) == [(1, 3), (3, 5)]  # touching is fine
    assert max_non_overlapping([]) == []
    print("ok")

TypeScript

max_non_overlapping.ts

import assert from "node:assert/strict";

type Interval = [number, number];

/** Largest set of pairwise non-overlapping half-open [s, e) intervals. */
export function maxNonOverlapping(intervals: Interval[]): Interval[] {
  const chosen: Interval[] = [];
  let lastEnd = -Infinity;
  const byEnd = [...intervals].sort((a, b) => a[1] - b[1]); // 1. earliest finish first
  for (const [s, e] of byEnd) {
    if (s >= lastEnd) { // 2. compatible with everything chosen
      chosen.push([s, e]); // 3. commit, never undo
      lastEnd = e;
    }
  }
  return chosen;
}

// The classic CLRS activity set (16.1): the optimum has 4 activities.
const acts: Interval[] = [[1, 4], [3, 5], [0, 6], [5, 7], [3, 9], [5, 9],
  [6, 10], [8, 11], [8, 12], [2, 14], [12, 16]];
assert.deepEqual(maxNonOverlapping(acts), [[1, 4], [5, 7], [8, 11], [12, 16]]);
assert.deepEqual(maxNonOverlapping([[1, 3], [3, 5]]), [[1, 3], [3, 5]]); // touching is fine
assert.deepEqual(maxNonOverlapping([]), []);
console.log("ok");

C#

max_non_overlapping.cs

// Largest set of pairwise non-overlapping half-open [s, e) intervals.
static List<(int S, int E)> MaxNonOverlapping((int S, int E)[] intervals)
{
    var chosen = new List<(int S, int E)>();
    int lastEnd = int.MinValue;
    foreach (var iv in intervals.OrderBy(iv => iv.E))   // 1. earliest finish first (stable)
    {
        if (iv.S >= lastEnd)                            // 2. compatible with everything chosen
        {
            chosen.Add(iv);                             // 3. commit, never undo
            lastEnd = iv.E;
        }
    }
    return chosen;
}

// The classic CLRS activity set (16.1): the optimum has 4 activities.
(int, int)[] acts = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9),
                     (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)];
var got = MaxNonOverlapping(acts);
if (!got.SequenceEqual([(1, 4), (5, 7), (8, 11), (12, 16)])) throw new Exception("wrong picks");
if (MaxNonOverlapping([(1, 3), (3, 5)]).Count != 2) throw new Exception("touching is fine");
if (MaxNonOverlapping([]).Count != 0) throw new Exception("expected none");
Console.WriteLine("ok");

Coin change shows the other side. “Largest coin first” is optimal for coin systems like 1, 5, 10, 25 (these are called canonical), and wrong for others. When you can’t prove it, a DP over amounts gives the true optimum.

Python

greedy_coins vs min_coins.py

def greedy_coins(coins: list[int], amount: int) -> list[int] | None:
    """Largest coin first. Fast, but only optimal for some coin systems."""
    picked: list[int] = []
    for c in sorted(coins, reverse=True):
        while c <= amount:          # 1. grab the biggest coin that still fits
            amount -= c
            picked.append(c)
    return picked if amount == 0 else None   # can get stuck, e.g. coins {3, 4}, amount 6


def min_coins(coins: list[int], amount: int) -> int:
    """True optimum by DP: best[a] = 1 + min(best[a - c]). -1 if impossible."""
    INF = amount + 1
    best = [0] + [INF] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                best[a] = min(best[a], best[a - c] + 1)   # 2. try every last coin
    return best[amount] if best[amount] < INF else -1


if __name__ == "__main__":
    assert greedy_coins([1, 5, 10, 25], 63) == [25, 25, 10, 1, 1, 1]
    assert len(greedy_coins([1, 5, 10, 25], 63)) == min_coins([1, 5, 10, 25], 63)  # canonical: greedy OK
    assert greedy_coins([1, 3, 4], 6) == [4, 1, 1]       # 3 coins...
    assert min_coins([1, 3, 4], 6) == 2                  # ...but 3 + 3 needs 2
    assert greedy_coins([3, 4], 6) is None and min_coins([3, 4], 6) == 2
    print("ok")

TypeScript

greedy_coins vs min_coins.ts

import assert from "node:assert/strict";

/** Largest coin first. Fast, but only optimal for some coin systems. */
export function greedyCoins(coins: number[], amount: number): number[] | null {
  const picked: number[] = [];
  for (const c of [...coins].sort((a, b) => b - a)) {
    while (c <= amount) { // 1. grab the biggest coin that still fits
      amount -= c;
      picked.push(c);
    }
  }
  return amount === 0 ? picked : null; // can get stuck, e.g. coins {3, 4}, amount 6
}

/** True optimum by DP: best[a] = 1 + min(best[a - c]). -1 if impossible. */
export function minCoins(coins: number[], amount: number): number {
  const INF = amount + 1;
  const best = new Array<number>(amount + 1).fill(INF);
  best[0] = 0;
  for (let a = 1; a <= amount; a++)
    for (const c of coins)
      if (c <= a) best[a] = Math.min(best[a], best[a - c] + 1); // 2. try every last coin
  return best[amount] < INF ? best[amount] : -1;
}

assert.deepEqual(greedyCoins([1, 5, 10, 25], 63), [25, 25, 10, 1, 1, 1]);
assert.equal(greedyCoins([1, 5, 10, 25], 63)!.length, minCoins([1, 5, 10, 25], 63)); // canonical: greedy OK
assert.deepEqual(greedyCoins([1, 3, 4], 6), [4, 1, 1]); // 3 coins...
assert.equal(minCoins([1, 3, 4], 6), 2); // ...but 3 + 3 needs 2
assert.equal(greedyCoins([3, 4], 6), null);
assert.equal(minCoins([3, 4], 6), 2);
console.log("ok");

C#

greedy_coins vs min_coins.cs

// Largest coin first. Fast, but only optimal for some coin systems.
static List<int>? GreedyCoins(int[] coins, int amount)
{
    var picked = new List<int>();
    foreach (int c in coins.OrderDescending())
        while (c <= amount)                 // 1. grab the biggest coin that still fits
        {
            amount -= c;
            picked.Add(c);
        }
    return amount == 0 ? picked : null;     // can get stuck, e.g. coins {3, 4}, amount 6
}

// True optimum by DP: best[a] = 1 + min(best[a - c]). -1 if impossible.
static int MinCoins(int[] coins, int amount)
{
    int inf = amount + 1;
    var best = new int[amount + 1];
    Array.Fill(best, inf);
    best[0] = 0;
    for (int a = 1; a <= amount; a++)
        foreach (int c in coins)
            if (c <= a) best[a] = Math.Min(best[a], best[a - c] + 1); // 2. try every last coin
    return best[amount] < inf ? best[amount] : -1;
}

if (!GreedyCoins([1, 5, 10, 25], 63)!.SequenceEqual([25, 25, 10, 1, 1, 1])) throw new Exception("greedy US coins");
if (GreedyCoins([1, 5, 10, 25], 63)!.Count != MinCoins([1, 5, 10, 25], 63)) throw new Exception("canonical: greedy is optimal");
if (GreedyCoins([1, 3, 4], 6)!.Count != 3) throw new Exception("greedy takes 4+1+1");
if (MinCoins([1, 3, 4], 6) != 2) throw new Exception("3+3 is optimal");
if (GreedyCoins([3, 4], 6) is not null || MinCoins([3, 4], 6) != 2) throw new Exception("greedy gets stuck");
Console.WriteLine("ok");

Test greedy against brute force

On small random inputs, compare your greedy against an exhaustive search (try every subset or ordering). If they ever disagree, you have a counterexample in seconds. It’s the fastest way to kill a wrong greedy idea, and a good thing to say you’d do.

What it costs

	Time	Space
Sort + one pass (most interval / scheduling greedies)	O(n log n)	O(n) for the sorted copy, O(1) extra otherwise
Greedy with a heap (choices change as you go)	O(n log n)	O(n)
Exhaustive search it replaces	O(2ⁿ) or O(n!)	O(n)
DP fallback when greedy fails (e.g. coin change)	O(n · amount)	O(amount)

Greedy is almost always the cheapest correct algorithm when it works. The price is the proof.

Variations you’ll meet

• Interval scheduling (this page): earliest finish.
• Interval partitioning / colouring (fewest resources so nothing clashes): process by start, reuse the resource that frees up earliest. The answer equals the maximum overlap, which ties it to the sweep line.
• Fractional knapsack: you may take part of an item, so sort by value per weight and fill. With whole items only (0/1 knapsack), the same rule fails: see knapsack.
• Scheduling to minimise lateness: earliest deadline first (exchange argument on adjacent inversions).
• Weighted interval scheduling (each interval has a value): no known greedy rule works, because one valuable long interval can beat many short ones. It needs dynamic programming.
• Greedy on a stack: “remove k digits to make the smallest number” keeps a monotonic stack.
• Matroids: the theory of when “sort by weight, take if independent” is always optimal (Kruskal’s MST is the famous instance).

Pitfalls

• Greedy by intuition. “Take the biggest / shortest / earliest” feels right and often isn’t. Find the exchange argument or a counterexample before you code.
• Wrong sort key. Sorting intervals by start for “max non-overlapping” is the classic wrong answer. By end is correct.
• Ties. Some greedy proofs need a specific tie-break (e.g. equal end times: any order is fine for activity selection, but not for every problem). Check.
• Weights sneak in. If items have values or weights, greedy usually stops working. Re-read the prompt.
• Touching endpoints. s >= last_end vs s > last_end depends on whether ranges are half-open. See intervals.
• Floating-point ratios. When sorting by a ratio like value/weight, compare a.v * b.w with b.v * a.w in integers to avoid precision bugs.

In the interview

• Say “I think a greedy works here” and then immediately justify it: either the exchange argument in two sentences, or “let me look for a counterexample first”.
• Try two or three plausible rules on a tiny example. Showing you rejected the wrong ones is strong signal.
• If you can’t prove it and a 4-item counterexample appears, switch to DP calmly. That pivot is itself a good outcome.
• Follow-ups to expect: “prove it”, “what if items have weights now?” (often DP), “return the chosen items, not just the count”, “what if inputs arrive one by one?” (online greedy, usually with a heap).

Check yourself

Check yourself

pick one

Intervals [0, 10), [1, 3), [4, 6), [7, 9). Which greedy rule fails to find the maximum number of non-overlapping intervals?

AEarliest finishBEarliest startCBoth find 3

Check yourself

pick one

Coins {1, 7, 10}, amount 14. What do largest-coin-first and the true optimum give?

ABoth give 2 coinsBGreedy 5 coins (10 + 1 + 1 + 1 + 1), optimum 2 coins (7 + 7)CGreedy 2 coins, optimum 2 coins but different ones

Check yourself

pick one

In the exchange argument for earliest-finish, why can the first interval of an optimal solution be swapped for the greedy one?

ABecause the greedy interval is shorterBBecause the greedy interval ends no later, so everything after the swapped-out interval still fitsCBecause optimal solutions are unique

Practice on your own

Classic exercises (not gym questions):

• Minimum number of arrows to burst all balloons (horizontal ranges).
• Assign cookies: each child needs a cookie of at least their greed factor; maximise happy children.
• Gas station: find the start index from which you can drive around a circular route.
• Minimise the sum of completion times on one machine (shortest job first) and prove it.
• Partition a string into as many pieces as possible so each letter appears in at most one piece.

Go deeper

• Introduction to Algorithms (CLRS), ch. 16 “Greedy Algorithms” (ch. 15 in the 4th edition): activity selection, the greedy-choice property, Huffman codes.
• Kleinberg and Tardos, Algorithm Design, ch. 4: “greedy stays ahead” and exchange-argument proofs, with interval scheduling and minimising lateness.
• Jeff Erickson, Algorithms, ch. 4 “Greedy Algorithms” (free online), including why most greedy ideas are wrong.

Related

IntervalsOverlap tests and the endpoint convention greedy relies on.

Dynamic programming: 1DWhat to switch to when greedy has a counterexample.

KnapsackWhere value-per-weight greedy breaks for whole items.

Minimum spanning treesKruskal and Prim: greedy with a proof.