Greedy Algorithms
DSA · Algorithm Techniques
Theory
A greedy algorithm builds a solution step by step, always taking the choice that looks best right now, without revisiting earlier decisions. It is fast and simple, but it only gives the optimal answer when the problem has the greedy-choice property, which you should justify (often by an exchange argument). Activity selection, Huffman coding, Dijkstra and Kruskal are greedy; coin change with arbitrary coins is a classic case where greedy fails.
Why we use it
When it works, greedy is usually the simplest and fastest correct solution, often O(n log n) due to sorting.
When to use it
Use greedy for interval scheduling, minimum platforms, fractional knapsack, Huffman coding and MSTs. Verify with a counterexample check before trusting it.
How it works
- Sort or order the choices
- Take the best-looking choice now
- Choice is valid? Yes: Add to solution. No: Skip it.
- More choices? Yes: Repeat. No: Done.
- Works only when local best leads to global best
Syntax
sort items by the key that makes the local choice safe
for item in items:
if item fits with choices so far: take it
Typical time: O(n log n)Example
meetings = [(1, 4), (3, 5), (0, 6), (5, 7), (8, 9), (5, 9)]
def max_meetings(meetings):
chosen, last_end = [], -1
for start, end in sorted(meetings, key=lambda m: m[1]):
if start >= last_end:
chosen.append((start, end))
last_end = end
return chosen
print("Meetings booked:", max_meetings(meetings))
def greedy_coins(amount, coins):
used = []
for c in sorted(coins, reverse=True):
while amount >= c:
amount -= c; used.append(c)
return used
print("Indian coins for 289:", greedy_coins(289, [1, 2, 5, 10, 20, 50, 100, 200]))
print("Greedy fails for 6 with [1,3,4]:", greedy_coins(6, [1, 3, 4]), "(best is [3, 3])")Key points
- Take the best local choice
- Never revisit decisions
- Must prove the greedy choice is safe
- Fast, often O(n log n)