Greedy algorithms
Greedy Algorithms
A greedy algorithm is a problem-solving strategy that builds up a solution piece by piece — always choosing the option that looks best right now, without worrying about the future consequences of that choice.
The word "greedy" is apt: the algorithm grabs the most attractive option at each step, pockets it, and moves on. There's no backtracking, no second-guessing, no looking ahead. Just one decisive move after another.
In one line: Make the locally optimal choice at each step and hope it leads to a globally optimal solution.
Think of it like eating the biggest slice of pizza first at a party. You're not thinking about whether someone else might want it — you're just making the best move for you, right now.
Greedy algorithms don't reconsider past decisions. Once a choice is made, it's final. This makes them fast and easy to implement, but not always correct for every problem — that's the tradeoff.
Why Use Greedy?
Fast Usually O(n log n) or better — much faster than dynamic programming. Simple Easy to code and understand. No complex state tracking needed. Optimal (sometimes) For certain problems, greedy always gives the correct answer.
Greedy works best when the problem has two properties:
1. Greedy Choice Property — A global solution can be reached by making locally optimal choices.
2. Optimal Substructure — An optimal solution contains optimal solutions to its sub-problems.
If these hold, greedy is your best friend. If not, you may need dynamic programming or backtracking instead.
A Simple Example – Coin Change
You need to give change of ₹36 using the fewest coins possible. Available coins: 25, 10, 5, 1.
The greedy approach: always pick the largest coin that fits.
| Step | Remaining | Coin Picked |
|---|---|---|
| 1 | 36 | 25 |
| 2 | 11 | 10 |
| 3 | 1 | 1 |
Result: 3 coins. Simple and optimal for standard coin systems.
def coin_change(coins, amount):
# Sort coins in descending order (largest first)
coins.sort(reverse=True)
result = []
for coin in coins:
# Use as many of this coin as possible
while amount >= coin:
amount -= coin
result.append(coin)
return result
# Example
coins = [25, 10, 5, 1]
amount = 36
print(coin_change(coins, amount))
# Output: [25, 10, 1] → 3 coins
Note: Greedy coin change only works for standard coin systems. For arbitrary denominations (e.g. coins = [1, 3, 4], amount = 6), greedy may fail. Use Dynamic Programming instead.
Popular Greedy Problems
Here are three classic problems where greedy shines — each with a clear explanation and clean Python code.
Activity Selection Problem
You have a list of activities, each with a start time and end time. You can only do one activity at a time. Pick the maximum number of activities you can attend.
Greedy idea: Always pick the activity that ends the earliest. This leaves the most room for future activities.
def activity_selection(activities):
# Sort activities by their end time
activities.sort(key=lambda x: x[1])
selected = [activities[0]]
last_end = activities[0][1]
for start, end in activities[1:]:
if start >= last_end: # no overlap
selected.append((start, end))
last_end = end
return selected
# (start, end) pairs
activities = [(1,4), (3,5), (0,6), (5,7), (3,9), (5,9), (6,10)]
print(activity_selection(activities))
# Output: [(1,4), (5,7), ...] — max non-overlapping activities
Fractional Knapsack
You have a bag with a weight limit. Items have a weight and value. You can take fractions of items. Maximize the total value you carry.
Greedy idea: Calculate value-per-unit-weight for each item. Always pick the item with the highest ratio first.
def fractional_knapsack(capacity, items):
# items = list of (value, weight)
# Sort by value-to-weight ratio, highest first
items.sort(key=lambda x: x[0] / x[1], reverse=True)
total_value = 0.0
for value, weight in items:
if capacity <= 0:
break
if weight <= capacity:
# Take the whole item
total_value += value
capacity -= weight
else:
# Take a fraction of the item
total_value += value * (capacity / weight)
capacity = 0
return round(total_value, 2)
Huffman Encoding
Given characters and their frequencies, build an optimal prefix code (binary tree) that minimizes total encoding length. Used in real-world compression (ZIP, JPEG).
Greedy idea: Always merge the two least frequent nodes. Characters used less get longer codes; frequent ones get shorter codes.
import heapq
def build_huffman(freq):
heap = [[weight, [char, ""]] for char, weight in freq.items()]
heapq.heapify(heap)
while len(heap) > 1:
lo = heapq.heappop(heap)
hi = heapq.heappop(heap)
# Assign '0' to left branch, '1' to right
for pair in lo[1:]: pair[1] = '0' + pair[1]
for pair in hi[1:]: pair[1] = '1' + pair[1]
heapq.heappush(heap, [lo[0] + hi[0]] + lo[1:] + hi[1:])
return sorted(heap[0][1:], key=lambda x: len(x[1]))
freq = {'a': 5, 'b': 9, 'c': 12, 'd': 13, 'e': 16, 'f': 45}
for char, code in build_huffman(freq):
print(f"{char}: {code}")
# f: 0 (most frequent → shortest code)
# a: 1100 (least frequent → longest code)
When NOT to Use Greedy
Greedy is not a silver bullet. It fails when local best choices don't lead to a global best. A classic example is the 0/1 Knapsack problem — where you can't split items, so grabbing the highest ratio item first may block a better combination.
| Problem | Greedy Works? | Better Approach |
|---|---|---|
| Activity Selection | ✅ Yes | — |
| Fractional Knapsack | ✅ Yes | — |
| Huffman Encoding | ✅ Yes | — |
| 0/1 Knapsack | ❌ No | Dynamic Programming |
| Shortest Path (general) | ❌ No | Dijkstra / Bellman-Ford |
| Coin Change (arbitrary) | ❌ No | Dynamic Programming |
Key Takeaways
Greedy algorithms are a powerful first tool to reach for. They're fast, easy to implement, and provably optimal for many classic problems. The key is recognising when the greedy choice property holds — and when you need to step up to dynamic programming.
A good rule of thumb: Can I prove that always picking the local best never hurts the global best? If yes — go greedy!
helpful
ReplyDelete