Greedy Algorithms

A greedy algorithm builds a solution one step at a time, always grabbing the choice that looks best right now — the locally optimal move — and never revisiting it. No backtracking, no exploring alternatives. Just commit and move on.

That sounds reckless, and sometimes it is. The whole discipline of greedy algorithms is knowing when a sequence of locally optimal choices adds up to a globally optimal answer. When it does, greedy is often the simplest and fastest tool you have. When it does not, it fails silently — returning a plausible but wrong answer.

When is greedy actually correct?

A greedy algorithm is provably correct when the problem has the greedy-choice property (a locally optimal choice is part of some globally optimal solution) and optimal substructure (an optimal solution contains optimal solutions to subproblems). The standard proof technique is the exchange argument: assume an optimal solution differs from the greedy one, then show you can swap in the greedy choice without making things worse — proving greedy is at least as good.

The canonical win — interval scheduling

Given a set of intervals, select the maximum number that do not overlap (the "activity selection" problem). The greedy rule is beautiful: sort by end time and always take the interval that finishes earliest among those still compatible. Finishing early leaves the most room for everything after it — that is the exchange argument in one sentence.

function maxNonOverlapping(intervals) {
  // sort by end time — the greedy choice
  intervals.sort((a, b) => a.end - b.end)

  let count = 0
  let lastEnd = -Infinity
  for (const { start, end } of intervals) {
    if (start >= lastEnd) { // compatible with what we've picked
      count++
      lastEnd = end
    }
  }
  return count
}

The sort dominates the runtime; the sweep is a single linear pass. Note the pattern: sort by the right key, then make one greedy pass. Picking the wrong sort key (say, shortest interval, or earliest start) breaks correctness — the choice of ordering is the algorithm.

When greedy lies — the coin change caveat

The famous counterexample: make change for an amount using the fewest coins. With US denominations (1, 5, 10, 25) the greedy "take the largest coin that fits" works. But with a set like , making 6 greedily gives 4 + 1 + 1 (three coins) while the optimum is 3 + 3 (two coins). Same algorithm, different denominations — one correct, one wrong. That is why coin change in general needs dynamic programming, not greed.

Greedy in the wild

• Interval / activity selection — sort by end time, sweep.
• Huffman coding — repeatedly merge the two least-frequent symbols via a min-heap to build an optimal prefix code.
• Dijkstra's shortest path — greedily finalize the nearest unvisited node; correct because edge weights are non-negative.
• Kruskal's / Prim's MST — greedily add the cheapest safe edge.
• Fractional knapsack — take items by best value-to-weight ratio (the 0/1 version is not greedy — it needs DP).