Lesson 30
Greedy Algorithms
Take the best-looking step now — and prove it never hurts later.
01Why it matters & the intuition
When a greedy choice is provably safe, it gives the simplest and fastest solution: interval scheduling, Huffman coding, minimum spanning trees and jump games. Knowing when greedy *fails* is equally important.
Think of it like…
Booking one meeting room for as many meetings as possible: always pick the meeting that ends earliest. It leaves the most time for everything else, so no other first choice can do better.
02See it move
Press play, then step through slowly. Change the input and predict the next frame before you click.
- considering
- booked
- skipped (overlap)
03Key ideas
Greedy choice property
A locally optimal choice is part of some globally optimal solution. You must argue this — it is not automatic.
Exchange argument
Take any optimal solution; swap its first choice for the greedy one and show it is still optimal. That proves greedy works.
When greedy fails
Coins {1, 3, 4} for amount 6: greedy takes 4 + 1 + 1 (3 coins), optimal is 3 + 3 (2 coins). That's a job for dynamic programming.
04Build it from scratch
A clean reference implementation. Read it line by line — then close it and write your own in the lab below.
// Max number of non-overlapping intervals [start, end).
function maxMeetings(intervals: [number, number][]): number {
const byEnd = [...intervals].sort((a, b) => a[1] - b[1]);
let count = 0;
let freeAt = -Infinity;
for (const [start, end] of byEnd) {
if (start >= freeAt) { count++; freeAt = end; } // earliest finish wins
}
return count;
}05Complexity
| Operation | Time | Space |
|---|---|---|
| Interval scheduling (sort by end) | O(n log n) | — |
| Jump game (track farthest reach) | O(n) | O(1) |
06Check your understanding
07Code lab
Write Python(or switch to JavaScript) and run it against real test cases. Python runs inside your browser — nothing is uploaded — and a C++ reference solution is under “Solution”.
Jump game
Write can_jump(nums). You start at index 0; nums[i] is the maximum jump length from i. Return true if you can reach the last index.