Skip to content

Greedy Algorithms Deep Dive

Understand greedy choice, proof techniques, and when greedy is optimal vs when it fails.

What you'll learn

  • The greedy choice property
  • Exchange argument proofs
  • Matroid theory and greedy optimality
  • Classic greedy problems: Huffman, activity selection

Concept

Greedy Algorithms Deep Dive

A greedy algorithm makes the locally optimal choice at each step, hoping to reach a globally optimal solution. It is simple and fast, but it only works when the problem has the greedy choice property (a local optimum is part of a global optimum) and optimal substructure.

Exchange Argument

The standard proof technique is the exchange argument: assume an optimal solution differs from the greedy one, then show you can swap elements to transform the optimal into the greedy without making it worse. This proves the greedy solution is at least as good as any optimal solution.

When Greedy Works

Greedy is provably optimal on problems with matroid structure - a mathematical framework where the greedy algorithm always finds the optimum. Minimum spanning tree (Kruskal), Huffman coding, and activity selection all have matroid structure.

When Greedy Fails

The 0/1 knapsack problem is the classic failure: greedy by value/weight ratio picks items that do not fit, missing the optimal combination. Fractional knapsack (where you can take fractions of items) does work with greedy.

Classic Examples

Activity selection: sort by finish time, greedily pick the next compatible activity. Huffman coding: repeatedly merge the two least-frequent symbols. Dijkstra: greedily expand the closest unvisited node.

Example

              // Activity selection - greedy by earliest finish time
function activitySelection(acts) {
  const sorted = acts.slice().sort((a, b) => a[1] - b[1]);
  const selected = [sorted[0]];
  for (let i = 1; i < sorted.length; i++) {
    if (sorted[i][0] >= selected[selected.length-1][1]) selected.push(sorted[i]);
  }
  return selected;
}
// Huffman coding - greedy merge of least frequent
function huffmanCodes(freqs) {
  const heap = freqs.map(([ch, f]) => ({ch, f, left: null, right: null}));
  while (heap.length > 1) {
    heap.sort((a, b) => a.f - b.f);
    const a = heap.shift(), b = heap.shift();
    heap.push({ch: null, f: a.f + b.f, left: a, right: b});
  }
  return heap[0];
}
const acts = [[1,4],[3,5],[0,6],[5,7],[3,9],[5,9],[6,10],[8,11],[8,12],[2,14],[12,16]];
console.log('Selected:', activitySelection(acts));
const tree = huffmanCodes([['a',45],['b',13],['c',12],['d',16],['e',9],['f',5]]);
console.log('Huffman root freq:', tree.f);
            

Activity selection sorts by finish time and greedily picks compatible activities. Huffman builds a tree by repeatedly merging the two least-frequent nodes.

Try it

  • Crontab Generator

    Scheduling is a greedy problem domain - see how interval scheduling works.

Common mistakes

The mistake

Assuming greedy is always optimal without proof.

The fix

Greedy works only for problems with the greedy choice property. Always prove optimality or verify with counterexamples.

The mistake

Sorting by the wrong criterion.

The fix

The sort key determines the greedy choice. Activity selection must sort by finish time, not start time. Wrong key means wrong answer.

Look up unfamiliar terms

A beginner-friendly glossary explains jargon in plain English — variables, functions, DOM, Promise, and more.

View glossary

Build real projects

Apply what you learned by building guided projects with starter code and solutions.

View projects

Decode error messages

Plain-English explanations of common errors — what they mean, why they happen, and how to fix them.

View errors