Greedy Algorithms

Greedy algorithms are deceptively elegant. You make one choice at a time — always the locally optimal one — and never reconsider. No tables, no memoization, no backtracking. When a greedy approach works, it produces clean, efficient, and easy-to-understand code.

The hard part is knowing when it works. A greedy algorithm that lacks a correctness proof is a bug waiting to happen. This chapter gives you both the intuition for designing greedy solutions and the mathematical framework for proving they are correct.

When Does Greedy Work?

A greedy approach produces an optimal solution when the problem has two properties:

1. Greedy Choice Property

A globally optimal solution can always be constructed by making the locally optimal choice at each step. You never need to reconsider a decision you’ve already made.

This is a strong claim. It says that being “short-sighted” — focusing only on what looks best right now — leads to the best overall outcome. Many problems do not have this property.

2. Optimal Substructure

After making the greedy choice, the remaining problem is a smaller instance of the same type, and its optimal solution combined with the greedy choice gives the globally optimal solution.

This property is shared with DP. The difference is that greedy commits to one choice (the best local one), while DP considers all choices and picks the best combination.

The Exchange Argument

How do you prove a greedy algorithm is correct? The standard technique is the exchange argument:

Suppose there exists an optimal solution $O$ that differs from the greedy solution $G$.
Find the first point where $O$ and $G$ differ — where $O$ makes a different choice.
Show that you can “exchange” $O$‘s choice for $G$‘s choice without making the solution worse.
Repeat this exchange process. After finitely many swaps, $O$ has been transformed into $G$ without any loss of optimality.
Conclude that $G$ is also optimal.

You don’t need to write formal proofs in an interview, but you do need to articulate the intuition: “Greedy works here because choosing the earliest ending interval never blocks a better option.”

Classic Greedy Problems

1. Activity Selection / Interval Scheduling

Problem: given $n$ intervals $[s_i, e_i)$, select the maximum number of non-overlapping intervals.

Greedy strategy: sort by end time. Always pick the interval that ends earliest and is compatible with the last selected interval.

Why it works: choosing the earliest-ending interval leaves the most room for future selections. If you instead chose a later-ending interval, it could only block more future options — never fewer.

record Interval(int start, int end) {}

List<Interval> activitySelection(List<Interval> intervals) {
    intervals.sort(Comparator.comparingInt(Interval::end));

    List<Interval> selected = new ArrayList<>();
    int lastEnd = Integer.MIN_VALUE;

    for (var interval : intervals) {
        if (interval.start() >= lastEnd) {
            selected.add(interval);
            lastEnd = interval.end();
        }
    }
    return selected;
}

Exchange argument sketch: Suppose the optimal solution’s first interval ends later than the greedy choice. Replace it with the greedy choice — it ends earlier, so it cannot conflict with any interval the optimal solution selects later. The exchanged solution has the same size and is still valid. Repeat for subsequent choices.

Time complexity: $O(n \log n)$ for sorting, $O(n)$ for the greedy scan.

2. Meeting Rooms II (Minimum Rooms)

Problem: given meeting intervals, find the minimum number of rooms needed so no two overlapping meetings share a room.

Greedy strategy: sort by start time. Use a min-heap tracking the earliest end time of rooms in use. If the current meeting starts after the earliest-ending room frees up, reuse that room; otherwise, allocate a new room.

int minMeetingRooms(int[][] intervals) {
    Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
    PriorityQueue<Integer> heap = new PriorityQueue<>(); // end times

    for (int[] meeting : intervals) {
        if (!heap.isEmpty() && heap.peek() <= meeting[0]) {
            heap.poll(); // reuse room
        }
        heap.offer(meeting[1]); // assign room
    }
    return heap.size();
}

The heap size at any point represents the number of concurrent meetings — the peak value is the answer.

Time complexity: $O(n \log n)$.

3. Jump Game

Problem: given an array nums where nums[i] is the maximum jump length from position i, determine if you can reach the last index starting from index 0.

Greedy strategy: track the farthest position reachable. Scan left to right; at each index, update the farthest reachable position. If you ever find yourself at an index beyond the farthest reachable, the answer is false.

boolean canJump(int[] nums) {
    int farthest = 0;
    for (int i = 0; i < nums.length; i++) {
        if (i > farthest) return false;
        farthest = Math.max(farthest, i + nums[i]);
    }
    return true;
}

Why it works: by always extending the farthest reachable boundary, you never miss a position that any strategy could reach. If the greedy can’t reach the end, no strategy can.

Time complexity: $O(n)$, single pass.

4. Huffman Coding

Problem: given characters with frequencies, build an optimal prefix-free binary encoding that minimizes the total encoded length.

Greedy strategy: repeatedly combine the two lowest-frequency symbols into a new node. The result is a binary tree where high-frequency characters have short codes and low-frequency characters have long codes.

sealed interface HuffmanNode permits Leaf, Internal {
    int frequency();
}

record Leaf(char symbol, int frequency) implements HuffmanNode {}

record Internal(HuffmanNode left, HuffmanNode right, int frequency)
        implements HuffmanNode {}

HuffmanNode buildHuffmanTree(Map<Character, Integer> freqMap) {
    PriorityQueue<HuffmanNode> pq = new PriorityQueue<>(
        Comparator.comparingInt(HuffmanNode::frequency)
    );

    for (var entry : freqMap.entrySet()) {
        pq.offer(new Leaf(entry.getKey(), entry.getValue()));
    }

    while (pq.size() > 1) {
        HuffmanNode left = pq.poll();
        HuffmanNode right = pq.poll();
        pq.offer(new Internal(left, right,
                              left.frequency() + right.frequency()));
    }

    return pq.poll();
}

void buildCodes(HuffmanNode node, String prefix,
                Map<Character, String> codes) {
    switch (node) {
        case Leaf leaf -> codes.put(leaf.symbol(), prefix);
        case Internal internal -> {
            buildCodes(internal.left(), prefix + "0", codes);
            buildCodes(internal.right(), prefix + "1", codes);
        }
    }
}

This uses Java 25’s sealed interfaces and pattern matching in switch. The HuffmanNode hierarchy is closed — every node is either a Leaf or an Internal node. Exhaustive pattern matching ensures the compiler verifies you handle both cases.

Why it works: combining the two least-frequent nodes ensures that the most frequent characters end up closest to the root, getting the shortest codes. The exchange argument shows that any tree with a more frequent node deeper than a less frequent node can be improved by swapping them.

Time complexity: $O(n \log n)$ where $n$ is the number of distinct characters.

5. Fractional Knapsack

Problem: given items with weights and values and a knapsack capacity, maximize total value. Unlike 0/1 Knapsack, you can take fractions of items.

Greedy strategy: sort items by value-to-weight ratio in decreasing order. Take as much of the highest-ratio item as possible, then move to the next.

record Item(double weight, double value) {
    double ratio() { return value / weight; }
}

double fractionalKnapsack(Item[] items, double capacity) {
    Arrays.sort(items, (a, b) -> Double.compare(b.ratio(), a.ratio()));

    double totalValue = 0.0;
    double remaining = capacity;

    for (var item : items) {
        if (remaining <= 0) break;

        double take = Math.min(item.weight(), remaining);
        totalValue += take * item.ratio();
        remaining -= take;
    }

    return totalValue;
}

Why it works: every unit of weight you fill generates the most value possible when you prioritize by ratio. Because fractions are allowed, there is no “wasted” capacity — you always fill the knapsack completely if total item weight exceeds capacity. The exchange argument: if the optimal solution takes less of a higher-ratio item and more of a lower-ratio item, swapping some weight from the lower to the higher ratio increases total value.

Time complexity: $O(n \log n)$ for sorting.

6. Task Scheduler

Problem: given tasks (represented as characters) and a cooldown period $n$, find the least number of intervals to execute all tasks, where the same task must have at least $n$ intervals between executions.

Greedy insight: the bottleneck is the most frequent task. Arrange the most frequent task first, then fill the gaps with other tasks.

Formula: let maxFreq be the highest frequency, and countMax be the number of tasks with that frequency. The minimum intervals are:

$$\text{result} = \max!\bigl(\text{total tasks},; (\text{maxFreq} - 1) \times (n + 1) + \text{countMax}\bigr)$$

int leastInterval(char[] tasks, int n) {
    int[] freq = new int[26];
    for (char task : tasks) freq[task - 'A']++;

    int maxFreq = 0;
    int countMax = 0;
    for (int f : freq) {
        if (f > maxFreq) {
            maxFreq = f;
            countMax = 1;
        } else if (f == maxFreq) {
            countMax++;
        }
    }

    int formulaResult = (maxFreq - 1) * (n + 1) + countMax;
    return Math.max(tasks.length, formulaResult);
}

Why it works: the (maxFreq - 1) blocks of size (n + 1) create the necessary cooldown gaps. The final countMax accounts for the last execution of each most-frequent task. When there are enough diverse tasks to fill all gaps, total tasks dominates the formula.

Time complexity: $O(n)$ where $n$ is the number of tasks.

When Greedy Fails

Greedy is not a universal tool. Here are prominent problems where it produces incorrect answers:

0/1 Knapsack: greedy by value-to-weight ratio fails. Consider items: {weight=1, value=6}, {weight=2, value=10}, {weight=3, value=12}, capacity = 5. Greedy picks items by ratio (6, 5, 4) and selects the first two (weight=3, value=16). But taking items 2 and 3 (weight=5, value=22) is better. The 0/1 constraint prevents splitting items, breaking the greedy choice property.

Coin Change (arbitrary denominations): with denominations {1, 3, 4} and target 6, greedy picks 4+1+1 = 3 coins. The optimal solution is 3+3 = 2 coins. Greedy works for standard US denominations because of their specific ratios, but fails in general.

Longest Path in a Graph: greedily extending the longest edge at each step does not produce the globally longest path.

The pattern: greedy fails when a locally good choice prevents you from accessing a globally better combination later. This is precisely when DP is needed — it considers all combinations.

Greedy vs DP Decision Guide

Question	If Yes →	If No →
Can I prove the greedy choice property?	Greedy	Try DP
Do I need to consider combinations of choices?	DP	Greedy is worth testing
Does a counterexample break the greedy approach?	DP	Greedy is safe
Are subproblems overlapping?	DP	Greedy or D&C

A practical strategy: start by asking “does greedy work?” Try a small example. If you find a counterexample, switch to DP. If you can’t find one, attempt an exchange argument. Even a 30-second intuition for why greedy works is better than no justification at all.

Interviewer Tips

Always state WHY greedy works. Even a brief sentence — “we sort by end time because choosing the earliest-ending interval leaves the most room” — shows depth. Interviewers are suspicious of greedy solutions without justification, because they know how often greedy fails.
Try counterexamples first. Before implementing a greedy solution, test it on a small example where the answer is known. If greedy produces the wrong answer, stop and rethink.
Know the classic greedy failures. 0/1 Knapsack and Coin Change with arbitrary denominations are the two most common traps. Mentioning them proactively demonstrates mastery.
Greedy is often the first step toward DP. If greedy fails, the structure of your greedy attempt often reveals the state and recurrence for a DP solution.
Keep greedy solutions clean. The beauty of greedy is simplicity. If your greedy solution has lots of special cases and conditions, you are likely forcing a paradigm that doesn’t fit.