Greedy Algorithms: When Grabbing the Best Right Now Actually Works

It’s a one-day film festival and the timetable is chaos — a dozen screenings scattered across the afternoon, all overlapping in awkward ways. You have exactly one goal: watch as many complete films as you physically can. Where do you even begin?

Here’s the instinct almost everyone reaches for, and it turns out to be a great one: don’t agonise over the whole grid. Just always walk into the movie that ends the soonest. The instant its credits roll, pick the next film that hasn’t started yet, again choosing whatever finishes earliest — and keep doing that until the day runs out. Follow that one dumb-sounding rule and, remarkably, you’ll leave having seen the largest number of films any human possibly could.

That "grab the best-looking option in front of you and never look back" move has a name — it’s a greedy algorithm — and it’s one of the fastest, most satisfying ideas in all of programming when it works. The catch is right there in that sentence: when it works. Sometimes grabbing the local best marches you straight to the global best. Sometimes it walks you off a cliff. By the end of this article you and I will have built a greedy that provably wins, watched one silently lose, and — the part most tutorials skip — learned how to actually tell the two apart.

Let’s start nowhere near a computer

Stay at the festival, because the whole idea lives here.

A greedy algorithm builds its answer one choice at a time. At each step it looks only at what’s in front of it right now, takes whatever looks best by some simple rule, commits, and never reconsiders. No branching, no backtracking, no "what if I’d chosen differently." Just: best-looking thing, grab it, move on.

For the festival, "best-looking" means ends soonest. And there’s a real reason that rule is smart, not just convenient: the movie that finishes earliest leaves the most daylight for everything after it. Every other choice you could make either finishes later (wasting time you’ll want) or starts earlier and collides with things you’ve already picked. Finishing early is the choice that keeps the most options alive. Hold that sentence — "the greedy pick leaves at least as much room as any other" — because it’s the seed of the only proof that matters here.

Now let me hand you the coin jar, because it’s where the same instinct betrays you. You owe a friend some money and want to pay with the fewest coins. The obvious greedy: keep handing over the biggest coin that still fits. With the coins in your pocket — 1, 2, 5, 10 — that works every single time; it’s literally how you make change without thinking. But swap in a stranger coin system and the exact same rule can hand back more coins than necessary. Same greedy spirit, opposite outcome.

So two everyday habits, one lesson: taking the locally-best choice sometimes reaches the globally-best answer and sometimes doesn’t. Everything in this article is about which of those two worlds you’re standing in — and how to know for sure before you write a line of code.

Where you already meet it

Once you see "commit to the best-looking option and never reconsider," it’s running quietly all over your day:

• Making change at any till — biggest coin (or note) first.
• Your calendar app fitting the most non-overlapping meetings into a room — the festival problem wearing a suit.
• CPU and disk schedulers picking the shortest job next to keep average wait low.
• Dijkstra’s algorithm settling the closest unvisited node first to find shortest paths — a greedy on graphs. (Walk through it in Dijkstra’s shortest path.)
• Kruskal’s minimum spanning tree — take the cheapest edge that doesn’t form a cycle, the greedy on top of union-find.

But the example that best shows how far this idea reaches is hiding inside a file you opened today. Huffman coding is the compression trick at the heart of every ZIP archive, every JPEG, every MP3. The problem: give each letter a binary code so that common letters get short codes and rare ones get long codes, making the whole file as small as possible. Huffman solves it with a startlingly simple greedy — repeatedly take the two least-frequent symbols and merge them into one combined symbol whose frequency is their sum, then repeat until a single tree remains. The two rarest things always get pushed deepest (longest codes); the frequent things stay near the top (short codes).

Here’s why it’s the perfect teacher, and not just another name-drop. Unlike the festival, "best right now" means the two smallest counts, not the earliest finish — the greedy rule changes shape to fit the problem. And Huffman’s greedy is provably optimal: it produces a code no scheme on earth can beat, and the proof is the same move we’re about to spend real time on. The two least-frequent symbols can always be slid to the deepest level of some optimal tree without hurting it — so committing to them early costs nothing. Same skeleton, richer object, and a proof that reappears verbatim. That single generalisation teaches more than five more "you’ve seen this" bullets ever could.

What it actually looks like

Let’s pin down the festival before we write anything. Here are six movies as bars on a shared timeline, and the set a greedy actually keeps.

Read the bars: they overlap in a tangle, but the three coloured ones — A, C, F — never touch each other. Greedy found them by the rule from the analogy: keep the movie that ends soonest (A, done at 3), then the next film that starts at or after that finish and itself ends soonest (C, starting at 4), then the next (F). Three whole films, and — we’ll prove it — no strategy on earth fits a fourth.

That’s the shape of every greedy: a simple ordering rule, a single sweep, a running "is this compatible with what I’ve already taken?" check. Because the expensive part is almost always the sort, a greedy typically runs in O(n log n) — the sweep itself is a linear O(n). Compare that to trying every possible subset of movies (O(2ⁿ), hopeless past twenty films) and you see the whole appeal: greedy is fast. The only question is whether it’s right.

Let’s build one, step by step

We’ll build the festival scheduler — called activity selection in the textbooks — assemble it, and then deliberately break a greedy so you feel the boundary.

Step 1 — the recipe: sort, sweep, take if compatible

Every greedy that solves this family has the same three-move skeleton:

1. Sort the items by the key your rule cares about (here: finish time).
2. Sweep through them once, keeping a tiny bit of state about what you’ve committed to (here: the finish time of the last movie you kept).
3. Take each item only if it’s compatible with that state (here: it starts at or after the last finish).

No item is ever revisited. That’s the promise — and the peril — of greedy: one pass, no takebacks.

Step 2 — activity selection: earliest finish wins

Sort the movies by finish time, then walk the list. Keep a movie only if it starts at or after the last finish you locked in.

Follow the sweep: A is taken (last finish becomes 3); B starts at 2, before 3, so it collides — skip. C starts at 4, clear — take it, last finish becomes 7. D and E both start before 7 — skip. F starts at 8 — take it. Done in one pass.

public static List<int[]> selectActivities(int[][] intervals) {
    int[][] a = intervals.clone();                 // don't reorder the caller's array
    Arrays.sort(a, (x, y) -> Integer.compare(x[1], y[1]));   // by finish time
    List<int[]> chosen = new ArrayList<>();
    int lastFinish = Integer.MIN_VALUE;
    for (int[] iv : a) {
        if (iv[0] >= lastFinish) {                 // compatible: starts after last finish
            chosen.add(iv);
            lastFinish = iv[1];
        }
    }
    return chosen;
}

The rule: among everything still compatible, the one that frees you soonest is always safe to take. That’s the whole algorithm — and it’s the claim we’re about to actually prove, because "seems reasonable" is exactly the trap the next step springs.

Step 3 — the bug: a plausible key that’s flatly wrong

Sorting by finish time feels arbitrary. Why not sort by shortest duration — grab the quick movies so you can fit more of them? It sounds at least as sensible. Watch it fail.

Three movies: A runs 1–5, B runs 4–6, C runs 5–9. The shortest is B (two hours), so shortest-first grabs it immediately — and B overlaps both A and C, so it blocks them both. You watch one film. But earliest-finish-first keeps A (ends at 5) and then C (starts at 5) for two. A perfectly reasonable-sounding rule cut your answer in half.

So we have two rules that sound equally plausible and give opposite answers. Feeling clever isn’t enough. We need a proof that earliest-finish is safe — and that proof is the one genuinely deep idea worth slowing all the way down for.

Why earliest-finish is safe: the exchange argument

Here’s the question that separates memorising the algorithm from owning it: how do you prove a greedy choice can’t possibly cost you the optimum? The standard weapon is called an exchange argument, and once you’ve seen it you’ll reach for it every time you meet a greedy.

The idea in one breath: take any optimal solution, and show you can edit it — swap one of its choices for the greedy’s choice — without making it any worse. If every optimal solution can be nudged to agree with greedy’s first pick at no cost, then there exists an optimal solution that starts with greedy’s pick. Repeat down the line, and greedy is optimal.

Let’s do it for activity selection. Call greedy’s picks g₁, g₂, … in the order it takes them, and let O = o₁, o₂, …, oₘ be any optimal set, sorted by finish time. Look at the first pick.

• g₁ is, by construction, the movie with the globally earliest finish time. So g₁ finishes no later than o₁: finish(g₁) ≤ finish(o₁).
• Now swap o₁ out of the optimal set and g₁ in. Is the result still valid? The only thing o₁ had to clear was o₂, and o₂ started at or after finish(o₁). Since finish(g₁) ≤ finish(o₁), o₂ starts at or after finish(g₁) too — so g₁ doesn’t collide with o₂ either.
• The edited set {g₁, o₂, …, oₘ} has the same size as O, so it’s still optimal — and now it agrees with greedy on the first choice.

That’s the exchange: one swap, provably no loss. Do it again on the remaining problem (the movies that start after g₁), and the same argument installs g₂, then g₃, and so on. An optimal solution has been transformed, choice by choice, into greedy’s solution without ever shrinking. Therefore greedy’s solution is optimal. There was never a fourth film to fit.

There’s a twin framing you’ll also hear, called greedy stays ahead. Instead of editing an optimal solution, you prove by induction that after i picks, greedy’s i-th movie finishes no later than the i-th movie of any solution:

Greedy is never "behind" — it always has at least as much of the day left. So it can never run out of room before an optimal solution does, which means it fits at least as many movies. Same truth, viewed from the other end: exchange bends the optimum toward greedy; stay-ahead shows greedy racing alongside the optimum and never trailing.

Where greedy falls apart

Now the other side of the boundary — because knowing when greedy breaks is the whole skill, and the counterexamples are burned into every interviewer’s memory.

Coin change: the biggest coin isn’t always right

Make the amount 6 from coins {1, 3, 4}, using as few coins as possible.

Greedy grabs the biggest coin that fits: a 4, leaving 2 — which only two 1s can cover. Three coins: 4 + 1 + 1. But the optimum skips the "obvious" 4 entirely and pays 3 + 3 — two coins. Greedy lost by taking the locally-best coin, because that 4 stranded it with a remainder no big coin could clean up.

/** Greedy: always take the largest coin that fits. Fast, but NOT always optimal. */
public static int coinChangeGreedy(int[] coins, int amount) {
    int[] c = coins.clone();
    Arrays.sort(c);                                // ascending; walk from the biggest down
    int count = 0, remaining = amount;
    for (int i = c.length - 1; i >= 0; i--) {
        while (remaining >= c[i]) {
            remaining -= c[i];
            count++;
        }
    }
    return remaining == 0 ? count : -1;            // -1 = greedy got stuck
}
 
/** DP: the true minimum number of coins, or -1 if the amount can't be made. */
public static int coinChangeDP(int[] coins, int amount) {
    int[] best = new int[amount + 1];
    Arrays.fill(best, amount + 1);                 // amount + 1 stands in for "infinity"
    best[0] = 0;
    for (int a = 1; a <= amount; a++) {
        for (int coin : coins) {
            if (coin <= a && best[a - coin] + 1 < best[a]) {
                best[a] = best[a - coin] + 1;      // reconsider EVERY coin at every amount
            }
        }
    }
    return best[amount] > amount ? -1 : best[amount];
}

Look at what the dynamic-programming version does differently: at every amount it tries every coin and remembers the best, instead of committing to one and marching on. That reconsidering is exactly what greedy refuses to do — and exactly what’s needed here. It costs O(amount × coins) time instead of O(coins log coins), and that extra work is the price of correctness on a system where greedy can’t be trusted.

Knapsack: the same greedy, right and then wrong

One more, because it draws the boundary in the sharpest possible line — the same greedy rule that’s provably optimal on one version is provably wrong on its near-twin.

You have a bag of capacity 50 and three items, each with a weight and a value. You want the most value. The natural greedy: sort by value per unit weight (the "density") and take the densest first.

• Fractional knapsack — you’re allowed to take slices of an item (think gold dust, or rice). Here the density greedy is provably optimal: fill up with the densest item, then the next, and top off the last gap with a fraction. You reach value 240, and nothing beats it — any swap toward a less-dense item only loses value per kilo.
• 0/1 knapsack — items are indivisible; it’s all or nothing (you can’t take half a laptop). Now the same density greedy loses. It grabs item 1 (w10) and item 2 (w20), filling 30 of the 50 units — but item 3 needs 30 units and only 20 are left, so it’s stranded. Greedy scores 160. The real optimum ignores the density order and takes items 2 and 3 for 220 — a combination greedy never even considers.

/** Fractional knapsack: greedy by value/weight ratio IS provably optimal. */
public static double fractionalKnapsack(int[] weight, int[] value, int capacity) {
    Integer[] idx = byRatioDesc(weight, value);
    double total = 0;
    int room = capacity;
    for (int i : idx) {
        if (weight[i] <= room) {                   // take the whole item
            total += value[i];
            room -= weight[i];
        } else {                                   // fill the last gap with a slice
            total += value[i] * ((double) room / weight[i]);
            break;
        }
    }
    return total;
}
 
/** 0/1 knapsack by the SAME ratio greedy — indivisible items, so it can lose. */
public static int knapsack01Greedy(int[] weight, int[] value, int capacity) {
    Integer[] idx = byRatioDesc(weight, value);
    int total = 0, room = capacity;
    for (int i : idx) {
        if (weight[i] <= room) {                   // all-or-nothing, no slices
            total += value[i];
            room -= weight[i];
        }
    }
    return total;
}

Why does divisibility flip the answer? Because fractional knapsack has the exchange property — if a solution ever prefers a less-dense unit of weight over a denser one, swap them and it improves, so the densest-first order is unbeatable. The 0/1 version loses that property: you can’t swap a sliver, only a whole item, and whole items don’t line up neatly with the capacity you have left. That single missing degree of freedom is the entire difference between a greedy that’s a theorem and a greedy that’s a bug.

Greedy vs. the alternatives

When greedy’s proof holds, nothing beats it. When it doesn’t, you fall back to the tools that consider more than one path. Here’s the ledger — n items, W the target amount or capacity.

The trade is speed against certainty. Greedy is the fastest by a wide margin — one sort and one sweep — but it only earns the right to be used once you can prove its choice is safe. Dynamic programming buys guaranteed optimality by reconsidering every option at every subproblem, at a real time cost. Brute force always works and is almost always too slow to ship, so its best job is as a truth oracle: run it on small inputs to sanity-check a greedy you’re unsure about. That last trick — greedy plus a brute-force check on tiny cases — is how you catch a wrong sort key before it reaches production.

The complete implementation

Everything above, assembled — the activity scheduler, both coin-change strategies, and all three knapsack variants side by side:

package dev.fiveyear.greedy;
 
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
 
public final class Greedy {
 
    private Greedy() {}
 
    // ---- Activity selection (interval scheduling) ----
 
    /** Max set of mutually-compatible activities, chosen by earliest finish time. */
    public static List<int[]> selectActivities(int[][] intervals) {
        int[][] a = intervals.clone();                 // don't reorder the caller's array
        Arrays.sort(a, (x, y) -> Integer.compare(x[1], y[1]));   // by finish time
        List<int[]> chosen = new ArrayList<>();
        int lastFinish = Integer.MIN_VALUE;
        for (int[] iv : a) {
            if (iv[0] >= lastFinish) {                 // compatible: starts after last finish
                chosen.add(iv);
                lastFinish = iv[1];
            }
        }
        return chosen;
    }
 
    // ---- Coin change: greedy (can fail) vs DP (always optimal) ----
 
    /** Greedy: always take the largest coin that fits. Fast, but NOT always optimal. */
    public static int coinChangeGreedy(int[] coins, int amount) {
        int[] c = coins.clone();
        Arrays.sort(c);                                // ascending; walk from the biggest down
        int count = 0, remaining = amount;
        for (int i = c.length - 1; i >= 0; i--) {
            while (remaining >= c[i]) {
                remaining -= c[i];
                count++;
            }
        }
        return remaining == 0 ? count : -1;            // -1 = greedy got stuck
    }
 
    /** DP: the true minimum number of coins, or -1 if the amount can't be made. */
    public static int coinChangeDP(int[] coins, int amount) {
        int[] best = new int[amount + 1];
        Arrays.fill(best, amount + 1);                 // amount + 1 stands in for "infinity"
        best[0] = 0;
        for (int a = 1; a <= amount; a++) {
            for (int coin : coins) {
                if (coin <= a && best[a - coin] + 1 < best[a]) {
                    best[a] = best[a - coin] + 1;
                }
            }
        }
        return best[amount] > amount ? -1 : best[amount];
    }
 
    // ---- Knapsack: fractional (greedy optimal) vs 0/1 (greedy fails) ----
 
    /** Fractional knapsack: greedy by value/weight ratio IS provably optimal. */
    public static double fractionalKnapsack(int[] weight, int[] value, int capacity) {
        Integer[] idx = byRatioDesc(weight, value);
        double total = 0;
        int room = capacity;
        for (int i : idx) {
            if (weight[i] <= room) {                   // take the whole item
                total += value[i];
                room -= weight[i];
            } else {                                   // fill the last gap with a slice
                total += value[i] * ((double) room / weight[i]);
                break;
            }
        }
        return total;
    }
 
    /** 0/1 knapsack by the SAME ratio greedy — indivisible items, so it can lose. */
    public static int knapsack01Greedy(int[] weight, int[] value, int capacity) {
        Integer[] idx = byRatioDesc(weight, value);
        int total = 0, room = capacity;
        for (int i : idx) {
            if (weight[i] <= room) {                   // all-or-nothing, no slices
                total += value[i];
                room -= weight[i];
            }
        }
        return total;
    }
 
    /** 0/1 knapsack, the true optimum by dynamic programming. */
    public static int knapsack01DP(int[] weight, int[] value, int capacity) {
        int[] best = new int[capacity + 1];
        for (int i = 0; i < weight.length; i++) {
            for (int c = capacity; c >= weight[i]; c--) {   // reverse: each item used once
                best[c] = Math.max(best[c], best[c - weight[i]] + value[i]);
            }
        }
        return best[capacity];
    }
 
    // item indices sorted by descending value/weight ratio
    private static Integer[] byRatioDesc(int[] weight, int[] value) {
        Integer[] idx = new Integer[weight.length];
        for (int i = 0; i < idx.length; i++) {
            idx[i] = i;
        }
        Arrays.sort(idx, (i, j) ->
            Double.compare((double) value[j] / weight[j], (double) value[i] / weight[i]));
        return idx;
    }
}

And here it is producing exactly the outputs the comments claim — greedy winning where it’s safe and losing where it isn’t:

// Activity selection: earliest-finish greedy is optimal here.
int[][] movies = {{1, 3}, {2, 5}, {4, 7}, {6, 8}, {5, 9}, {8, 10}};
Greedy.selectActivities(movies).size();          // 3   — the films A, C, F (finishes 3, 7, 10)
 
// Coin change: greedy is WRONG on {1, 3, 4} for 6.
Greedy.coinChangeGreedy(new int[]{1, 3, 4}, 6);  // 3   — 4 + 1 + 1
Greedy.coinChangeDP(new int[]{1, 3, 4}, 6);      // 2   — 3 + 3  (the true minimum)
 
// Coin change: greedy is RIGHT on a canonical system {1, 2, 5, 10}.
Greedy.coinChangeGreedy(new int[]{1, 2, 5, 10}, 6); // 2   — 5 + 1
Greedy.coinChangeDP(new int[]{1, 2, 5, 10}, 6);     // 2   — greedy matches DP
 
// Knapsack: fractional greedy is optimal; 0/1 greedy loses to DP.
int[] w = {10, 20, 30}, v = {60, 100, 120};
Greedy.fractionalKnapsack(w, v, 50);             // 240.0 — optimal (2/3 of item 3)
Greedy.knapsack01Greedy(w, v, 50);               // 160   — greedy, and wrong
Greedy.knapsack01DP(w, v, 50);                   // 220   — the true 0/1 optimum

The two coinChange lines on {1, 2, 5, 10} are the whole lesson in miniature: on a canonical system greedy and DP agree, so greedy is the right, faster choice — and on {1, 3, 4} they diverge, and only DP tells the truth. Nothing in the greedy code changed; only the input did.

The interview corner

Greedy problems are an interviewer’s favourite trap: the naive greedy is easy to write and often looks right on the examples, so the real test is whether you know to prove it — or to reject it. Walk in ready for exactly that.

Ask these before you write a line:

• "Do I actually need the optimum, or is a good-enough answer fine?" If approximate is acceptable, a greedy is often the pragmatic pick even without a proof. If it must be optimal, you owe a proof or a DP.
• "Are the items divisible or all-or-nothing?" This one question decides knapsack for you: fractional → greedy by density is optimal; 0/1 → greedy is wrong, reach for DP. Say it out loud; it shows you know the boundary.
• "What exactly am I sorting by, and is there a tie-break?" The sort key is the algorithm. Name it explicitly — "earliest finish, ties broken by earliest start" — because a plausible-but-wrong key is the classic way to fail this round.

The follow-up ladder — where a strong candidate keeps climbing:

1. "Prove your greedy is correct." Give the exchange argument: take any optimal solution, swap in the greedy’s first choice, show the swap loses nothing, induct. Or state the stay-ahead invariant. Naming "greedy-choice property + optimal substructure" signals you’ve done this before.
2. "Now the items are indivisible — 0/1 knapsack." The density greedy breaks; switch to DP in O(n · W). Flag that it’s only pseudo-polynomial (it scales with the numeric capacity W, not just n), and that 0/1 knapsack is NP-hard in general.
3. "Minimise total waiting time for jobs on one machine." Sort by shortest processing time first — a textbook exchange-argument greedy: if any two adjacent jobs are out of order, swapping them lowers total wait, so the sorted order is optimal.
4. "Build an optimal prefix code / merge k sorted files cheaply." That’s Huffman: repeatedly pull the two smallest with a min-heap and merge, O(n log n). The heap is the "best right now" engine — see heaps and priority queues.
5. "The coin denominations are arbitrary — is greedy safe?" No — only canonical systems guarantee it, and you can’t eyeball canonicity. Verify it with DP, or run greedy against a DP oracle on small amounts and watch them diverge.

Three mistakes that fail the round:

• Assuming greedy is correct because it works on your examples. "It passed the samples" is not a proof — the interviewer picked samples greedy survives, then hands you {1, 3, 4}. Prove it or don’t claim it.
• Sorting by the wrong key. Shortest-duration or earliest-start for interval scheduling returns confidently wrong, smaller answers. Derive the key from a swap argument, not from what sounds reasonable.
• Using greedy where the items are indivisible. Density-first is a theorem for fractional knapsack and a bug for 0/1. Conflating the two is the single most common knapsack error.

Where to go from here

You now own the core: a greedy takes the locally-best choice and never looks back — blazing fast, but correct only when an exchange argument says the greedy pick can’t cost you the optimum. Three natural next stops:

• Dynamic programming — the tool for exactly the problems greedy can’t touch: 0/1 knapsack, arbitrary coin change, anything where you must reconsider instead of commit. It’s the other half of this coin.
• Huffman coding, Kruskal, and Prim — provably-correct greedies worth memorising cold. Kruskal is a greedy riding on union-find; Dijkstra is a greedy on weighted graphs in Dijkstra’s shortest path.
• Matroid theory — the deep answer to "when is greedy optimal?" It turns out greedy is guaranteed optimal on exactly the structures called matroids, which is why interval scheduling and spanning trees yield to it and knapsack doesn’t.

Next time you walk into the earliest-ending movie at a festival, or hand over the biggest coin at a till, you’ll know you’re running a greedy — and, more importantly, you’ll know whether it’s about to win.