Greedy Algorithms
Think of it like this
You're at a buffet with limited plate space. At each dish, you ask: "Is this worth the space?" If yes, take it; if not, skip it. You never go back to reconsider a dish you already passed.
That's greedy: make the locally best decision at each step, never reconsidering past choices. The trick is knowing when local-best guarantees global-best.
Greedy often fails: taking the most expensive item first doesn't guarantee the most valuable backpack (0/1 knapsack requires DP). But in carefully structured problems, it's provably optimal and far simpler than DP.
When Does Greedy Work?
A greedy algorithm is correct when the problem has the greedy choice property: a locally optimal choice is always part of some globally optimal solution.
This is proved using an exchange argument: assume an optimal solution doesn't make the greedy choice → show you can swap to the greedy choice without making it worse → contradiction → greedy is at least as good.
Pattern 1, Activity Selection / Interval Scheduling
Select the maximum number of non-overlapping intervals.
Greedy strategy: always pick the interval that ends earliest. Why? An interval that ends earlier leaves more room for future intervals.
Intervals: [1,4], [2,3], [3,5], [4,6], [6,8]
Sort by end time: [2,3], [1,4], [3,5], [4,6], [6,8]
Pick [2,3] (ends at 3, no conflict)
Skip [1,4] (starts at 1 < 3, overlaps)
Pick [3,5] (starts at 3 ≥ 3, no conflict)
Skip [4,6] (starts at 4 < 5, overlaps)
Pick [6,8] (starts at 6 ≥ 5, no conflict)
Result: 3 intervals ✓ (optimal)function eraseOverlapIntervals(intervals) {
if (!intervals.length) return 0;
intervals.sort((a, b) => a[1] - b[1]); // sort by END time
let count = 0, end = -Infinity;
for (const [start, stop] of intervals) {
if (start >= end) {
end = stop; // take this interval
} else {
count++; // skip (remove) this interval
}
}
return count; // number of removals
}
// Meeting Rooms II, minimum rooms needed
function minMeetingRooms(intervals) {
const starts = intervals.map(i => i[0]).sort((a, b) => a - b);
const ends = intervals.map(i => i[1]).sort((a, b) => a - b);
let rooms = 0, maxRooms = 0, e = 0;
for (let s = 0; s < starts.length; s++) {
if (starts[s] < ends[e]) rooms++; // new meeting starts before any ends → need room
else { rooms--; e++; } // a meeting ended, reuse that room
maxRooms = Math.max(maxRooms, rooms);
}
return maxRooms;
}Pattern 2, Jump Game
Can you reach the last index? What is the minimum number of jumps?
Greedy: at each position, track the farthest you can reach. If you can't reach the current position, you're stuck.
nums = [2, 3, 1, 1, 4] (value = max jump from that index)
Position 0: can reach up to 0+2=2
Position 1: can reach up to 1+3=4 (beyond end) → YES ✓// Can reach end?, O(n) greedy
function canJump(nums) {
let maxReach = 0;
for (let i = 0; i < nums.length; i++) {
if (i > maxReach) return false; // stuck, can't reach position i
maxReach = Math.max(maxReach, i + nums[i]);
}
return true;
}
// Minimum jumps to reach end, O(n) greedy
function jumpMinimum(nums) {
let jumps = 0, currentEnd = 0, farthest = 0;