DSA · Chapter 36 of 40
Greedy Algorithms
A greedy algorithm makes the locally best choice at each step and never reconsiders. It is fast and simple, but it only produces the optimal answer when the problem has the greedy-choice property.
Activity selection, interval merging, coin change with canonical coin systems, and Huffman coding are classic greedy problems.
Proving greed works
Show an exchange argument: any optimal solution can be transformed into the greedy one without getting worse.
When greed fails
Coin change with coins [1, 3, 4] and amount 6: greedy picks 4+1+1 = 3 coins, but the optimum is 3+3 = 2 coins. Use DP instead.
Example 1 (python)
def max_meetings(intervals):
intervals.sort(key=lambda x: x[1])
end, count = float('-inf'), 0
for s, e in intervals:
if s >= end:
count += 1
end = e
return count
print(max_meetings([(1, 3), (2, 4), (3, 5)]))Output
2Sorting by finish time is the greedy key for activity selection.
Example 2 (python)
def merge_intervals(iv):
iv.sort()
out = [iv[0]]
for s, e in iv[1:]:
if s <= out[-1][1]:
out[-1] = (out[-1][0], max(out[-1][1], e))
else:
out.append((s, e))
return out
print(merge_intervals([(1, 3), (2, 6), (8, 10)]))Output
[(1, 6), (8, 10)]Sorting by start time makes merging a single pass.
Key points
- Greedy takes the best local choice and never backtracks.
- Sorting is almost always the first step.
- It needs the greedy-choice property to be correct.
- When greed fails, dynamic programming usually works.
💡 Note: Always sanity-check a greedy idea against a small counterexample before committing.