Greedy Algorithms

A greedy algorithm takes the best-looking option at each step and never reconsiders. No backtracking, no table, no second-guessing — which makes it the simplest and fastest technique here, and the easiest to be quietly wrong with.

When it works

Greedy is correct when the problem has the greedy choice property: a locally optimal choice is always part of some globally optimal solution.

That is a real mathematical property, not a hunch, and it either holds or it does not. When it does not, greedy does not fail loudly — it returns a plausible, wrong answer. That is what makes it worth being careful with.

A case where it is provably right

Interval scheduling: given a set of intervals, pick the most that do not overlap.

    public static int maxNonOverlapping(Interval[] intervals) {
        if (intervals.length == 0) {
            return 0;
        }
        Interval[] sorted = intervals.clone();
        Arrays.sort(sorted, Comparator.comparingInt(Interval::end));

        int count = 0;
        int lastEnd = Integer.MIN_VALUE;
        for (Interval interval : sorted) {
            if (interval.start() >= lastEnd) {
                count++;
                lastEnd = interval.end();
            }
        }
        return count;
    }

Sort by end time, then take everything that fits. The proof sketch: whatever the optimal solution is, swapping its first interval for the earliest-finishing one cannot make things worse — it leaves at least as much room for the rest. Repeat, and you have transformed the optimal solution into the greedy one without losing anything.

The instructive part is the near-misses. Sorting by start time looks just as reasonable and is wrong: one long interval starting first blocks everything. Sorting by duration also sounds sensible and is also wrong. Only "earliest finish" has the proof, and this is the case the test pins:

        Check.eq(maxNonOverlapping(new Interval[] {
            new Interval(1, 10), new Interval(2, 3), new Interval(4, 5),
        }), 2, "the long one is correctly skipped");

The record Interval(int start, int end) is Java 25 pulling its weight: a value carrier with equality, a constructor and accessors in one line.

⚠️ A case where it is wrong

    public static int coinChangeGreedy(int[] coins, int amount) {
        int[] descending = coins.clone();
        Arrays.sort(descending);
        int count = 0;
        int remaining = amount;
        for (int i = descending.length - 1; i >= 0; i--) {
            while (remaining >= descending[i]) {
                remaining -= descending[i];
                count++;
            }
        }
        return remaining == 0 ? count : -1;
    }

Take the biggest coin that fits, repeatedly. With US coins it is correct and it is what every cashier does. With coins {1, 3, 4} making 6, it takes 4, then 1, then 1 — three coins, when two threes would do.

Both algorithms run in the same test, so the two posts cannot drift apart on the one example that matters:

        // The headline result: greedy and DP disagree, and DP is the correct one.
        Check.eq(coinChangeGreedy(new int[] {1, 3, 4}, 6), 3, "greedy takes 4+1+1");
        Check.eq(DynamicProgramming.coinChange(new int[] {1, 3, 4}, 6), 2, "DP finds 3+3");

Nothing throws. Nothing warns. The greedy answer is simply worse, and if you had only ever tested with US coins you would never know. Coin systems where greedy always works are called canonical, and most real currencies are — which is exactly why this bug hides so well.

The pair that shows the boundary

Knapsack makes the distinction crisp, because the same problem flips depending on one rule.

Fractional knapsack — items can be cut. Greedy is optimal: take the best value-per-weight first, and fill any leftover space with a fraction.

        // Best value per unit of weight first.
        Arrays.sort(order, (a, b) -> Double.compare(
                (double) values[b] / weights[b], (double) values[a] / weights[a]));

0/1 knapsack — items are whole or not at all. Greedy breaks immediately: the best ratio might be a small item, and taking it can leave space nothing fits into. DP is required.

Same items, same capacity, one rule different — and the correct technique changes. Whether you can take a fraction is exactly whether the greedy choice property holds.

Greedy against dynamic programming

When greedy is valid it is strictly better — faster, simpler, no memory. The entire question is whether it is valid.

Greedy algorithms worth knowing

• Dijkstra's shortest path — always expand the nearest unvisited vertex. Correct with non-negative weights; incorrect with negative ones, which is a greedy failure in the wild.
• Huffman coding — repeatedly merge the two least frequent symbols. Provably optimal.
• Kruskal and Prim — minimum spanning trees, both greedy, both proved.
• Activity selection — the interval scheduling above.

Notice how many carry a proof. That is the pattern: a greedy algorithm worth trusting comes with an argument for why the local choice is safe, not with a table of test cases that happened to pass.

How to decide

1. Write the greedy solution — it is usually a sort plus a loop.
2. Try to break it. Hunt for a small counter-example, the way {1, 3, 4} breaks coin change.
3. Found one? Use DP.
4. Cannot find one? Try to prove the exchange argument. "I could not think of a counter-example" is not the same as "there is none".

What to remember

• Take the local best, never reconsider.
• Correct only with the greedy choice property — otherwise it is quietly, plausibly wrong.
• Coin change with {1, 3, 4} making 6 is the counter-example to keep in your pocket.
• Fractional knapsack is greedy; 0/1 knapsack is DP.
• Attack your own greedy solution with a counter-example before trusting it.