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.
Build real projects
Apply what you learned by building guided projects with starter code and solutions.
Decode error messages
Plain-English explanations of common errors — what they mean, why they happen, and how to fix them.