Greedy Algorithms

Grab the best, keep going

A [[greedy-algorithm|greedy algorithm]] builds a solution one step at a time, and at every step it makes the choice that looks best *right now* — the biggest coin, the earliest-finishing meeting, the cheapest edge — and never reconsiders. There's no looking ahead and no backing up. It is the most optimistic strategy in all of computing: it simply trusts that a chain of locally-best choices will add up to a globally-best answer.

When that trust is justified, the payoff is enormous. Greedy algorithms are usually short, usually fast — often just *sort the inputs, then sweep through them once* — and they sidestep the heavy machinery of dynamic programming entirely. You'll meet two structures you already know that are built on greedy choices: a minimum spanning tree (always add the cheapest safe edge) and Dijkstra's shortest path (always settle the nearest unfinished node next).

When greedy works: interval scheduling

Here's the classic win. You have a room and a pile of meetings, each with a start and end time; you want to fit in as many non-overlapping meetings as possible. The greedy rule that works is surprising: *always pick the meeting that finishes earliest among those that still fit.* Finishing early leaves the most room for everything after it. Sort by end time, then sweep.

#include <vector>
#include <algorithm>
struct Meeting { int start, end; };

int maxMeetings(std::vector<Meeting> v) {
    // Greedy: sort by EARLIEST finishing time.
    std::sort(v.begin(), v.end(),
              [](const Meeting& a, const Meeting& b){ return a.end < b.end; });

    int count = 0, lastEnd = -1;
    for (const Meeting& m : v) {
        if (m.start >= lastEnd) {   // doesn't overlap what we kept
            count++;
            lastEnd = m.end;        // commit; never reconsider
        }
    }
    return count;
}

Why is this *provably* optimal? The intuition is an exchange argument: take any best-possible schedule, and look at its first meeting. If it doesn't finish as early as the greedy first pick, you can swap in the greedy one — it ends no later, so it can't break anything that came after. Repeat the swap down the line, and you've turned an optimal schedule into the greedy one without ever losing a meeting. So greedy is at least as good as the best — meaning it *is* the best.

When greedy FAILS: the coin counterexample

Now the trap. To make change for an amount using the fewest coins, the obvious greedy rule is *grab the largest coin that fits, repeat.* With everyday coins {1, 5, 10, 25} it always works. But change the coin set and it breaks. Suppose your coins are {1, 3, 4} and you must make 6:

Coins available: { 1, 3, 4 }     Target: 6

GREEDY (take biggest first):        OPTIMAL:
    take 4   ->  remaining 2            take 3   ->  remaining 3
    take 1   ->  remaining 1            take 3   ->  remaining 0
    take 1   ->  remaining 0
    -----------------------             -----------------------
    4 + 1 + 1  =  THREE coins           3 + 3  =  TWO coins   (better!)

A second win: Huffman coding

One more place greedy shines: Huffman coding, the idea behind a lot of file compression. You want short bit-codes for frequent letters and longer ones for rare letters. The greedy move: repeatedly take the two least-frequent items, merge them into one node whose frequency is their sum, and put it back. Do that until one tree remains — and that tree gives provably optimal codes.

1. Put every symbol, with its frequency, into a min-priority queue (smallest frequency on top).
2. Pop the two smallest. Make a new node whose frequency is their sum and whose children are those two.
3. Push that merged node back into the queue.
4. Repeat until one node remains — the root of the Huffman tree. Left = 0, right = 1 gives each symbol its code.

Notice the engine: a min-heap-backed priority queue, exactly the structure from the previous rung. Greedy algorithms lean on sorting and priority queues constantly, because both let you cheaply ask "what's the best choice right now?" — which is the only question greedy ever asks.