Greedy Algorithms

The greedy mindset: commit and move on

Most optimization strategies hedge. Backtracking tries every option; dynamic programming computes the best result of every option before combining them. Greedy does neither: at each decision point it applies a simple rule (take the largest, the cheapest, the earliest-ending) commits permanently, and moves to the next decision. No undo, no table of alternatives.

That commitment is what makes greedy fast. There is no tree of possibilities to explore, just one path from start to finish, so the running time is typically O(n log n) for an initial sort plus O(n) for the pass. It is also what makes greedy dangerous: if an early choice turns out to block a better future, there is no mechanism to recover.

So a greedy algorithm is only correct when the problem has the greedy-choice property: some locally best choice is always safe, meaning it is part of at least one globally optimal solution. That property is a fact about the problem, not the code, and it is exactly what you must convince yourself (and your interviewer) of before trusting a greedy answer.

Activity selection: greedy done right

The classic showcase: given meetings with start and end times and one room, attend the maximum number of non-overlapping meetings. Several greedy rules sound plausible. Pick the shortest meeting? the one starting earliest? Both fail on simple examples (a short meeting straddling two long ones kills both; an early starter can hog the whole day).

The rule that works: always pick the meeting that ends earliest, discard everything overlapping it, and repeat. The intuition is an exchange argument: consider any optimal schedule, and look at its first meeting. Swapping it for the earliest-ending meeting can only free the room sooner, so everything else in that schedule still fits. The swap never makes things worse. Therefore choosing the earliest finisher is always safe.

The implementation is exactly the greedy signature: sort by end time, sweep once, keep a meeting whenever it starts at or after the last kept meeting's end. O(n log n) total, a few lines of code, provably optimal.

static int maxMeetings(int[][] meetings) {
    Arrays.sort(meetings, (a, b) -> a[1] - b[1]);
    int count = 0;
    int lastEnd = Integer.MIN_VALUE;
    for (int[] m : meetings) {
        if (m[0] >= lastEnd) {
            count++;
            lastEnd = m[1];
        }
    }
    return count;
}

When greedy fails: the coin trap

Now the impostor. Make an amount with the fewest coins, denominations 1, 3, and 4, target 6. Greedy grabs the biggest coin first: take 4 (2 left), take 1, take 1. Three coins. But the optimum is 3 + 3, two coins. Greedy's early grab of the 4 locked it out of the better pairing, and with no undo mechanism, it never found out.

Note the subtlety: with denominations 1, 5, 10, 25 the biggest-first rule happens to be optimal, which is why the change-making instinct feels universal. Whether greedy works depends on the specific numbers, not on the problem's general shape. That is what makes greedy treacherous. The same code is correct on one input family and wrong on another.

Coin change with arbitrary denominations needs dynamic programming: for each amount from 1 to the target, try every coin and keep the best, storing results in a table. DP wins here precisely because it does not commit. It evaluates all options for every subamount before choosing.

static int minCoins(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, Integer.MAX_VALUE - 1);
    dp[0] = 0;
    for (int a = 1; a <= amount; a++) {
        for (int c : coins) {
            if (c <= a) dp[a] = Math.min(dp[a], dp[a - c] + 1);
        }
    }
    return dp[amount];
}

Greedy or DP? A field guide

Both handle optimization problems with step-by-step choices, so telling them apart is the real skill. Greedy is the special case where one choice per step is provably safe; DP is the general case where you must compare outcomes of all choices because an inferior-looking option now can enable a superior future.

Practical workflow in an interview: first try to invent a greedy rule and immediately attack it with small adversarial examples, the way the 1-3-4 coins broke biggest-first. If you find a counterexample, pivot to DP with a clear conscience. If every attack fails, sketch an exchange argument (any optimal solution can be rewritten, without loss, to start with the greedy choice) and proceed. Saying this reasoning out loud earns more credit than silently guessing right.

Famous problems where greedy is proven correct and worth memorizing: activity or interval selection (sort by end time), Jump Game (track the farthest reachable index), Assign Cookies, and the merging logic in interval problems. Meanwhile Coin Change, House Robber, and Longest Increasing Subsequence look tempting but demand DP. With backtracking, DP, and greedy in hand, you now own the three classic strategies for choice-based problems. The final lesson assembles them into a repeatable framework for attacking any problem cold.

Frequently asked