Greedy Algorithms

The 10-second versionCopy Anchor Link

A greedy algorithm builds a solution one choice at a time, always taking the choice that looks best right now, and never reconsidering. No backtracking, no looking ahead. Shockingly, this is often optimal — but only when the problem has two specific properties: the greedy-choice property (a locally best choice can be part of a globally best solution) and optimal substructure (the rest of the problem is the same kind of problem, smaller). Miss either one and greedy doesn't just get a worse answer — it gets the wrong answer. The whole skill is knowing which side of that line you're on.

Why this existedCopy Anchor Link

The greedy instinct is as old as trade: when you're packing a bag, you take the most valuable thing that fits first and worry about the rest later. Turning that instinct into an algorithm people could trust took a run of famous breakthroughs in the 1950s.

• 1952 — David Huffman, a graduate student in Robert Fano's information-theory class at MIT, is told to either write a term paper or take a final exam. He writes the paper — and invents Huffman coding, a greedy rule for building optimal variable-length codes. (His own professor's earlier method was only close to optimal; the student beat the teacher.)
• 1956 — Two greedy classics land in the same year: Joseph Kruskal publishes his minimum spanning tree algorithm, and Edsger Dijkstra designs the shortest-path algorithm that still bears his name.
• 1957 — Richard Rado starts characterizing when greedy is provably optimal, a line of work Jack Edmonds completes in 1971 with matroids — the abstract structure that says "greedy is safe here."
• 1962 — the interval scheduling / activity-selection problem gets its clean greedy rule and its classic exchange argument proof, which becomes the template for proving greedy algorithms correct to this day.

Why it mattered then: greedy algorithms are fast — typically sorting plus a single pass — and in the 1950s "fast" was the difference between a computation finishing and not. The catch, discovered piece by piece, is that greedy is only valid when you can prove it is. The exchange argument became that proof.

Inside the inventor's headCopy Anchor Link

Take activity selection — the cleanest greedy problem there is. You have a list of activities, each with a start and a finish time, and a single room. You want to schedule the maximum number of non-overlapping activities. (Replace "activities" with "meetings" and "room" with "conference room" and it's a real calendar problem.)

The instinct fires immediately: there must be a rule for picking the first activity. Watch each plausible rule die:

Look at why each rule fails. Earliest start grabs a monster that blocks the whole day. Shortest grabs a small meeting that cuts across two neat back-to-back ones. Both mistakes are the same mistake: they optimize the present and wreck the future.

The pivot is what feels backwards at first. Instead of asking "which activity is best?" ask "which activity leaves me the most room for the rest?" The activity that finishes earliest is the one that minimizes how much of the timeline it consumes — so everything you might schedule next is still available. That single reframing — optimize for the future you leave open, not the item you take — is the greedy "aha."

Here's the trap in code. Both snippets pick a first activity; only one is correct:

// WRONG: greedily take the earliest-starting activityconst firstWrong = (acts) =>  acts.reduce((best, a) => (a.start < best.start ? a : best));// RIGHT: take the earliest-FINISHING activityconst firstRight = (acts) =>  acts.reduce((best, a) => (a.finish < best.finish ? a : best));

The final approachCopy Anchor Link

The two properties that make greedy legalCopy Anchor Link

Greedy is correct exactly when both of these hold:

• Greedy-choice property — you can reach some optimal solution by making the locally best first choice, then solving what's left. You don't need greedy to match every optimal solution, just to be able to build one.
• Optimal substructure — after you commit to that choice, the remaining problem is the same kind of problem on a smaller input, and an optimal solution to the whole contains optimal solutions to the parts.

For activity selection, the greedy choice is "earliest finish" and the remaining problem is "activity selection on activities starting after it." Both properties hold — and the exchange argument is how we prove the first one.

The algorithm, top to bottomCopy Anchor Link

The invariant and the proof by exchangeCopy Anchor Link

The invariant: last_end always holds the finish time of the most recent activity in our set, and every chosen activity starts at or after the previous one's finish. So the set is always feasible (no overlaps) after every step.

To prove it's maximal, we exchange. Let g₁ be the first activity greedy picks — the one with the earliest finish overall. Let O be any optimal schedule, and let o₁ be its first activity. Because g₁ finishes no later than o₁ does (finish(g₁) ≤ finish(o₁)), g₁ conflicts with no more of the remaining activities than o₁ does. So we can swap g₁ into O in place of o₁ and O stays just as large. Now repeat the argument on the activities that start after g₁ — the subproblem. Greedy matches the optimum at every step, so the whole is optimal.

A worked traceCopy Anchor Link

Activities [start, finish]:

Sort by finish, then scan left to right with last_end = 0:

• a1 [1,4] — start 1 ≥ 0, take. last_end = 4.
• a2 [3,5], a3 [0,6] — start below 4, skip.
• a4 [5,7] — 5 ≥ 4, take. last_end = 7.
• a5–a7 — start below 7, skip.
• a8 [8,11] — 8 ≥ 7, take. last_end = 11.
• a9 [8,12] — start below 11, skip.
• a11 [12,16] — 12 ≥ 11, take.

Result: {a1, a4, a8, a11} — 4 activities, which is the optimum.

The full implementationCopy Anchor Link

function maxActivities(activities) {  const sorted = [...activities].sort((a, b) => a.finish - b.finish);  const chosen = [];  let lastEnd = -Infinity;  for (const act of sorted) {    if (act.start >= lastEnd) {      chosen.push(act);      lastEnd = act.finish;    }  }  return chosen;}

ComplexityCopy Anchor Link

Compare that to the brute-force alternative — try every subset of activities and check for conflicts — which is Θ(2ⁿ). Greedy turns exponential into n log n when it's valid.

Where greedy is a trapCopy Anchor Link

Here is the same instinct leading off a cliff. Coin change: make a target amount with the fewest coins. Greedy says "always take the biggest coin that fits."

With the familiar denominations {1, 5, 10, 25} that works. With the weird ones {1, 3, 4} it collapses. Target 6:

Greedy takes the biggest coin, 4, and then is stuck with two 1s — three coins. The real answer is two coins, 3 + 3. Greedy-choice property violated: the locally biggest coin wasn't part of the globally best solution. There is no coin denomination for which you can patch this with a tie-break; greedy simply cannot see the future here.

This is the tell. Whenever the "best right now" choice can lock you out of a better combination later, greedy is the wrong tool — and you reach for dynamic programming, which considers every coin on purpose. We get there in the next pages, but this counterexample is why DP exists.

Where you meet it todayCopy Anchor Link

• File compression. Huffman coding is greedy on frequency: repeatedly merge the two rarest symbols. Every ZIP, JPEG, and MP3 you've ever opened leaned on it.
• Networking. Dijkstra's shortest path and Kruskal's/Prim's minimum spanning trees are greedy, and they route packets and lay out cable links.
• Calendars and scheduling. "Maximum number of meetings in one room" is activity selection; the earliest-finish rule is running in your calendar's "find a time" feature.
• Cache eviction. The optimal page-replacement policy (Bélády's) is greedy on "replace what won't be used for the longest" — provably optimal, and a useful yardstick even though it needs the future to be known.

// Greedily merge the two least-frequent nodes -- the core of Huffman coding.function twoSmallest(freq) {  let a = 0, b = -1;  for (let i = 1; i < freq.length; i++) if (freq[i] < freq[a]) a = i;  for (let i = 0; i < freq.length; i++)    if (i !== a && (b < 0 || freq[i] < freq[b])) b = i;  return [a, b];}

RecapCopy Anchor Link

• Greedy makes one irreversible choice at a time, taking what looks best now — no backtracking.
• It's only optimal when the problem has the greedy-choice property and optimal substructure; otherwise it's confidently wrong.
• The exchange argument is the standard proof: show a locally best first choice can be swapped into an optimal solution without shrinking it.
• Activity selection works because earliest-finish leaves the most room; earliest-start and shortest-first both fail.
• Coin change with {1, 3, 4} is the warning shot — when greedy fails, dynamic programming is next.

Next up: Backtracking — when you do need to explore and reconsider, done systematically instead of greedily.