So far, most of our algorithms have been about exploring possibilities - systematically (recursion/backtracking). But some problems have a special property: the best choice right now is also the best choice overall.
Think of making change with US coins. To make 67 cents, you'd grab a quarter (25), another quarter (50), a dime (60), a nickel (65), and two pennies (67). That's greedy - at each step, take the largest coin that doesn't exceed the target. And it works for US denominations.
But greedy doesn't always work. With denominations [1, 3, 4], making 6 cents: greedy says 4+1+1 (3 coins), but optimal is 3+3 (2 coins).
The art of greedy algorithms is knowing when to trust your greedy instinct and when to fall back to exploration.
A greedy algorithm makes the best choice at each step without considering future consequences.
When greedy works:
When greedy fails:
Classic greedy problems:
// GREEDY WORKS: Activity selection
// Choose the activity with the earliest end time
int MaxActivities(int[][] intervals) {
Array.Sort(intervals, (a, b) => a[1].CompareTo(b[1]));
int count = 1;
int end = intervals[0][1];
for (int i = 1; i < intervals.Length; i++) {
if (intervals[i][0] >= end) {
count++;
end = intervals[i][1];
}
}
return count;
} // O(n log n) - greedy choice (earliest end) is optimal
// GREEDY FAILS: Coin change with denominations [1, 3, 4], target 6
// Greedy: 4 + 1 + 1 = 3 coins
// Optimal: 3 + 3 = 2 coins (greedy fails here)Interval problems are a common interview category. They typically involve sorting by start or end time then scanning.
Common interval operations:
| Operation | Approach |
|---|---|
| Merge overlapping | Sort by start, extend if overlap |
| Count non-overlapping | Sort by end, count non-overlapping |
| Find min rooms needed | Sweep line (start+1, end-1) |
| Insert interval | Find insertion point, merge if needed |
Key insight: Almost all interval problems start with sorting.
// Merge Intervals - O(n log n)
int[][] Merge(int[][] intervals) {
Array.Sort(intervals, (a, b) => a[0].CompareTo(b[0]));
var merged = new List<int[]>();
int[] curr = intervals[0];
for (int i = 1; i < intervals.Length; i++) {
if (intervals[i][0] <= curr[1]) {
curr[1] = Math.Max(curr[1], intervals[i][1]);
} else {
merged.Add(curr);
curr = intervals[i];
}
}
merged.Add(curr);
return merged.ToArray();
}
// Non-overlapping intervals (remove min to make non-overlapping) - O(n log n)
int EraseOverlapIntervals(int[][] intervals) {
Array.Sort(intervals, (a, b) => a[1].CompareTo(b[1]));
int count = 0;
int end = intervals[0][1];
for (int i = 1; i < intervals.Length; i++) {
if (intervals[i][0] < end) count++;
else end = intervals[i][1];
}
return count;
}
// Min meeting rooms (min platforms) - O(n log n)
int MinMeetingRooms(int[][] intervals) {
var starts = intervals.Select(i => i[0]).OrderBy(x => x).ToArray();
var ends = intervals.Select(i => i[1]).OrderBy(x => x).ToArray();
int rooms = 0, endIdx = 0;
for (int i = 0; i < starts.Length; i++) {
if (starts[i] < ends[endIdx]) rooms++;
else endIdx++;
}
return rooms;
}Pattern 1: "Can you reach the end?" (Jump Game): At each position, track the furthest you can reach. If you ever pass that point, fail.
Pattern 2: "Maximum profit" (Stock): Buy low, sell high. Track minimum seen so far.
Pattern 3: "Minimum number of arrows/coins/platforms": Sort by end, greedily place the endpoint.
Pattern 4: "Largest/smallest number from digits": Build digit by digit, maintaining constraints.
// Jump Game - O(n)
bool CanJump(int[] nums) {
int maxReach = 0;
for (int i = 0; i < nums.Length; i++) {
if (i > maxReach) return false;
maxReach = Math.Max(maxReach, i + nums[i]);
}
return true;
}
// Best Time to Buy/Sell Stock (single transaction) - O(n)
int MaxProfit(int[] prices) {
int minPrice = int.MaxValue;
int maxProfit = 0;
foreach (var price in prices) {
if (price < minPrice) minPrice = price;
else maxProfit = Math.Max(maxProfit, price - minPrice);
}
return maxProfit;
}
// Jump Game II (minimum jumps) - O(n)
int Jump(int[] nums) {
int jumps = 0, currEnd = 0, farthest = 0;
for (int i = 0; i < nums.Length - 1; i++) {
farthest = Math.Max(farthest, i + nums[i]);
if (i == currEnd) {
jumps++;
currEnd = farthest;
}
}
return jumps;
}Greedy works when a local best choice is always the global best choice.
Greedy is the right tool when:
Greedy FAILS when:
Decision guide:
| Signal | Likely greedy? | Why |
|---|---|---|
| "Earliest finish time" | Yes | Classic interval scheduling |
| "Minimum number of coins" | No (with arbitrary denominations) | Must explore combinations |
| "Can you reach the end?" | Yes | Jump Game (greedy) |
| "Maximum profit with unlimited trades" | Yes | Stock II (greedy) |
| "Maximum profit with cooldown" | No | Need to explore rest combinations |
| "Minimum path sum" | No | Must compare different paths |
| "Schedule to maximize meetings" | Yes | Earliest finish time |
| "Knapsack (0/1)" | No | Must consider all combinations |
Rule of thumb: If you can prove that the optimal solution always includes the locally optimal choice, go greedy. If unsure, start by exploring all possibilities and optimize later.
"Greedy always works" - it doesn't: Greedy only works when the greedy choice property holds. Classic counterexample: coin change with denominations [1, 3, 4] for target 6. Greedy picks 4+1+1 (3 coins), but optimal is 3+3 (2 coins).
Not proving the greedy choice before coding: Before writing greedy code, ask: "Can I prove that the locally optimal choice is always part of the globally optimal solution?" If not, consider exploring all possibilities instead.
Sorting by the wrong property: For interval scheduling, sort by end time. For merge intervals, sort by start time. Sorting by the wrong key gives wrong intervals.
Using greedy when exploration is required: Problem signals that greedy likely won't work: "minimum cost with constraints", "all possible ways", "with exactly k items", "with a budget". These usually need backtracking or exploring all combinations.
Forgetting to update the tracked value in greedy algorithms: In interval scheduling: after picking an interval, update the current end time. In Jump Game: after reaching the current end, update the next jump boundary. Stale tracking values cause wrong results.
Greedy algorithms are a powerful addition to your mental toolbox - sometimes the best choice really is the greedy one. You've learned to spot problems where a simple rule (sort by end time, buy every dip, jump as far as possible) leads to the optimal answer.
But many real-world problems involve connections and relationships that can't be solved with a single greedy pass. For that, you need Graphs - the most flexible data structure of all. Social networks, road maps, and dependency graphs all require graph algorithms like BFS, DFS, and topological sort.
Next up: Graphs