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 (needs DP)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) | Need DP |
| "Can you reach the end?" | Yes | Jump Game (greedy) |
| "Maximum profit with unlimited trades" | Yes | Stock II (greedy) |
| "Maximum profit with cooldown" | No | Need DP |
| "Minimum path sum" | No | Dijkstra is greedy, general path is DP |
| "Schedule to maximize meetings" | Yes | Earliest finish time |
| "Knapsack (0/1)" | No | Must consider all combinations (DP) |
Rule of thumb: If you can prove that the optimal solution always includes the locally optimal choice, go greedy. If unsure, start with DP 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). This needs DP.
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 DP.
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 DP 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 DP or backtracking.
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.