Part 7 · 1 chapters · ~8 min

Greedy Algorithms

The greedy-choice property and exchange arguments, interval scheduling, Huffman coding, Dijkstra and Prim as greedy algorithms, when greedy fails (with counterexamples), and greedy heuristics for hard problems.

When the locally best choice is globally best

A greedy algorithm makes the best-looking choice at each step and never reconsiders. It is correct only when the problem has the greedy-choice property, usually proven with an exchange argument: any optimal solution can be transformed, step by step, into the greedy one without getting worse.

code

// interval scheduling: the maximum number of non-overlapping meetings → sort by END time, take greedily
function maxMeetings(ms: [number, number][]): number {
  let count = 0, end = -Infinity;
  for (const [s, e] of [...ms].sort((x, y) => x[1] - y[1])) if (s >= end) { count++; end = e; }
  return count;
}
// sorting by START time or by shortest duration both fail on some inputs: the choice of greedy rule is everything

greedy works	greedy fails
interval scheduling by earliest end	coin change with arbitrary denominations ({1, 3, 4})
Huffman coding (merge two rarest symbols)	0/1 knapsack (taking best value-per-weight first)
Dijkstra with non-negative weights	Dijkstra with negative weights
Kruskal and Prim for MST	travelling salesman (nearest neighbour is only a heuristic)

For NP-hard problems (Theory of Computation, course 27), greedy algorithms are often used as heuristics: fast, good-enough answers without guarantees.