Greedy Algorithms
Make the best local choice at every step and never look back. Interval scheduling, the exchange argument, and how to spot when greedy fails.
intermediate40 min#greedy#intervals#proofs#optimization
Prerequisites: Sorting
Why it matters
Greedy algorithms are the fastest and simplest way to optimize when they work. They run in a single pass or a sort, usually O(n log n), and the code is short. Scheduling, compression (Huffman coding), shortest paths (Dijkstra), and minimum spanning trees (Kruskal, Prim) are all greedy. The danger is that greedy looks right far more often than it is right. Knowing how to prove it, or find a counterexample, is the real skill.
Intuition
You are packing a bag for a trip and must pick items one at a time. A greedy packer always grabs the item with the best ratio of usefulness to size right now. Sometimes this gives the perfect bag. Other times an early good-looking choice blocks a better combination later.
Greedy works when two properties hold:
- Greedy-choice property: some optimal solution contains your local best choice.
- Optimal substructure: after making that choice, what remains is a smaller problem of the same kind.
If the first property fails, you need dynamic programming or search instead.
How it works
The typical greedy recipe: decide an ordering, then sweep once, keeping a choice only if it stays valid.
Example: interval scheduling. Given meetings with start and end times, attend as many non-overlapping meetings as possible. Candidate rules:
- Earliest start first? A long meeting starting at 0 can block everything.
- Shortest first? A short meeting in the middle can block two longer ones that fit side by side.
- Fewest conflicts first? Also has counterexamples.
- Earliest finish first: correct. Finishing early leaves the most room for the rest.
time: 0 1 2 3 4 5 6 7 8 9 10 11
A [---] start 1, end 4
B [-] start 3, end 5 overlaps A, ends later
C [-----] start 0, end 6 overlaps A
D [-] start 5, end 7
E [-] start 8, end 11
pick A (ends 4), skip B and C, pick D (5 >= 4), pick E.
Here is max_meetings on the same eight meetings as the code. Green meetings are kept, amber is the one being examined, faded ones were skipped.
One pass over the sorted list with a single variable, last_end. Each meeting is either kept or skipped, never revisited. The result is 3 meetings.
The exchange argument is the standard proof technique. Take any optimal solution OPT. Look at its first meeting X. Our greedy picks G, which ends no later than X. Replace X with G in OPT: it still has no overlap (G finishes at or before X, so nothing after is disturbed) and has the same size. So an optimal solution that starts with greedy's choice exists. Repeat on the rest by induction. The pattern: show you can swap any optimal choice for the greedy one without making things worse.
When greedy fails. With coins of 1, 5, and 6 and amount 10, taking the biggest coin first gives 6 + 1 + 1 + 1 + 1 (5 coins), but 5 + 5 uses 2. The greedy-choice property is false here: the largest coin is not in any optimal solution. For standard currency like 1, 5, 10, 25, greedy happens to be optimal, but that is a property of that coin system and must not be assumed.
Watch the largest-coin-first rule on amount 10 with coins 1, 5 and 6.
Greedy commits to 6 and can never undo it. Dynamic programming would try every coin at every amount and find the 2-coin answer.
How to test a greedy idea quickly: try to break it with a tiny input (3 to 5 items) before trusting it, and attempt the exchange argument. If you cannot explain the swap, suspect DP.
| Operation | Time | Notes |
|---|---|---|
| Sort by key, then one sweep | O(n log n) | Sorting dominates the work |
| Interval scheduling | O(n log n) | Sort by end time |
| Greedy with a heap (e.g. merging, scheduling) | O(n log n) | Each heap operation is O(log n) |
| Extra space | O(1) to O(n) | Often just a few variables |
Code: scheduling, coins, and jumping
def max_meetings(intervals):
count, last_end = 0, float("-inf")
for start, end in sorted(intervals, key=lambda iv: iv[1]): # earliest finish first
if start >= last_end:
count += 1
last_end = end
return count
def greedy_coins(coins, amount):
used = 0
for c in sorted(coins, reverse=True):
used += amount // c
amount %= c
return used if amount == 0 else -1
def can_jump(nums):
reach = 0
for i, step in enumerate(nums):
if i > reach:
return False
reach = max(reach, i + step)
return True
meetings = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11)]
print(max_meetings(meetings))
print(greedy_coins([1, 5, 10, 25], 63), greedy_coins([1, 5, 6], 10))
print(str(can_jump([2, 3, 1, 1, 4])).lower(), str(can_jump([3, 2, 1, 0, 4])).lower())function maxMeetings(intervals) {
let count = 0, lastEnd = -Infinity;
const sorted = [...intervals].sort((a, b) => a[1] - b[1]); // earliest finish first
for (const [start, end] of sorted) {
if (start >= lastEnd) {
count++;
lastEnd = end;
}
}
return count;
}
function greedyCoins(coins, amount) {
let used = 0;
for (const c of [...coins].sort((a, b) => b - a)) {
used += Math.floor(amount / c);
amount %= c;
}
return amount === 0 ? used : -1;
}
function canJump(nums) {
let reach = 0;
for (let i = 0; i < nums.length; i++) {
if (i > reach) return false;
reach = Math.max(reach, i + nums[i]);
}
return true;
}
const meetings = [[1, 4], [3, 5], [0, 6], [5, 7], [3, 9], [5, 9], [6, 10], [8, 11]];
console.log(maxMeetings(meetings));
console.log(greedyCoins([1, 5, 10, 25], 63), greedyCoins([1, 5, 6], 10));
console.log(canJump([2, 3, 1, 1, 4]), canJump([3, 2, 1, 0, 4]));Both versions print three lines: 3 (the greedy picks the meetings 1 to 4, 5 to 7, and 8 to 11), 6 5 (63 cents takes six coins with 1, 5, 10, 25, but amount 10 with coins 1, 5, 6 takes five, which is not optimal), and true false (the jump game results for two sample arrays).
Common pitfalls
- Choosing the wrong sort key: the whole algorithm is the ordering. Earliest finish works for maximizing count; for minimizing rooms needed you sweep by start time with a heap of end times.
- Strict versus non-strict overlap: decide whether meetings that touch (end equals start) conflict. The code above allows
start >= last_end. - Not sorting copies: sorting the input in place can surprise callers. Sort a copy if the order matters.
- Assuming a proof from a few examples: passing three tests is not evidence. Look for a counterexample on tiny cases.
- Confusing greedy with heuristics: a greedy that is not proven optimal is an approximation. That is fine in practice, but say so.
Practice
Assign cookies easy
Hint
Sort children by greed and cookies by size. Give the smallest cookie that satisfies the least greedy child.
Show solution
Sort both lists. Walk through cookies with a pointer into children; whenever a cookie is at least as big as the current child's greed, assign it and advance the child pointer. O(n log n) for the sorts.
Jump game medium
Hint
You do not need the exact path. Track the farthest index you can reach so far.
Show solution
Keep reach, starting at 0. For each index i, if i > reach return false; else set reach = max(reach, i + nums[i]). If you finish the loop, return true. O(n) time, O(1) space. The exchange idea: any index within reach is reachable, and a farther reach never hurts.
Minimum number of meeting rooms medium
Hint
Sort by start. Keep a min-heap of end times of rooms in use.
Show solution
Sort meetings by start. For each, if the earliest-ending room (heap top) has end time at most the new start, pop it (reuse the room). Push the new end time. The heap size at the end is the number of rooms. O(n log n).
Gas station hard
Hint
If total gas is less than total cost, no start works. Otherwise, what does it mean when your running tank goes negative at station i?
Show solution
If the total is non-negative a solution exists. Sweep with a running tank; when it drops below zero at station i, no start between the old start and i can work (each would have had at least as much deficit by then), so restart at i + 1. The last restart is the answer. O(n) time, O(1) space.
Interview questions
- How do you prove a greedy algorithm is correct? Usually an exchange argument: show any optimal solution can be transformed to include the greedy choice without getting worse. Another route is showing the greedy stays ahead of any alternative at every step.
- Why does earliest-finish-first work for interval scheduling but earliest-start-first does not? An early start may belong to a very long interval that blocks many others, while an early finish always leaves maximum room.
- Give a problem where greedy fails. Coin change with coins 1, 5, 6 for amount 10, or 0/1 knapsack by value-to-weight ratio.
- How do you choose between greedy and DP? If you can prove the greedy-choice property, use greedy (faster). If a locally best choice can block a better global one, use DP.
Interviewers look for: stating the sort key and justifying it, naming a counterexample for tempting wrong rules, and giving complexity (usually dominated by sorting).
Quick check
You want to attend the maximum number of non-overlapping meetings. Which greedy rule is correct?
Finished this lesson?
Further resources
- Greedy algorithm (Wikipedia) (article)
- Activity selection problem (Wikipedia) (article)
- Matroid (Wikipedia) (article)