Greedy Algorithms: Strategy and Applications
A greedy algorithm builds a solution incrementally, making the locally optimal choice at each step without reconsidering previous decisions. It's the algorithmic equivalent of always taking the...
Key Insights
- Greedy algorithms make locally optimal choices at each step, trading guaranteed global optimality for dramatic performance gains—but they only work when problems exhibit the greedy choice property and optimal substructure.
- The difference between a correct greedy solution and a wrong one often comes down to sorting strategy: interval scheduling works when sorted by end time, not start time or duration.
- Use greedy algorithms as your first attempt for optimization problems, but always validate with counterexamples before trusting the solution in production.
What Makes an Algorithm “Greedy”
A greedy algorithm builds a solution incrementally, making the locally optimal choice at each step without reconsidering previous decisions. It’s the algorithmic equivalent of always taking the biggest bill when making change—simple, fast, and often correct.
This stands in stark contrast to other approaches. Dynamic programming considers all possible subproblems and combines their solutions, storing intermediate results to avoid redundant computation. Brute force exhaustively explores every possible solution. Greedy algorithms do neither—they commit to choices immediately and never look back.
This aggressive strategy works brilliantly when two conditions hold: optimal substructure (an optimal solution contains optimal solutions to subproblems) and the greedy choice property (a locally optimal choice leads to a globally optimal solution). When these conditions don’t hold, greedy algorithms fail spectacularly.
The coin change problem illustrates this perfectly. With US currency denominations (25, 10, 5, 1 cents), greedily taking the largest coin that fits always produces the minimum number of coins. But change the denominations to (1, 3, 4) and try to make 6 cents: greedy picks 4+1+1 (three coins), while the optimal solution is 3+3 (two coins).
The Greedy Choice Property
Before implementing a greedy solution, you need to prove it’s correct. Two techniques dominate this space.
The exchange argument shows that any optimal solution can be transformed into the greedy solution without losing optimality. You demonstrate that swapping a non-greedy choice for a greedy one never makes the solution worse.
The greedy stays ahead argument proves that at every step, the greedy solution is at least as good as any other partial solution. By induction, this means the final greedy solution is optimal.
Here’s the coin change problem demonstrating when greedy works versus when it fails:
def greedy_coin_change(amount: int, denominations: list[int]) -> list[int]:
"""
Greedy coin change - works for canonical coin systems only.
Returns list of coins used, or empty list if impossible.
"""
denominations = sorted(denominations, reverse=True)
coins_used = []
for coin in denominations:
while amount >= coin:
coins_used.append(coin)
amount -= coin
return coins_used if amount == 0 else []
def dp_coin_change(amount: int, denominations: list[int]) -> list[int]:
"""
Dynamic programming coin change - always finds optimal solution.
"""
dp = [float('inf')] * (amount + 1)
dp[0] = 0
parent = [-1] * (amount + 1)
for i in range(1, amount + 1):
for coin in denominations:
if coin <= i and dp[i - coin] + 1 < dp[i]:
dp[i] = dp[i - coin] + 1
parent[i] = coin
if dp[amount] == float('inf'):
return []
# Reconstruct solution
coins_used = []
current = amount
while current > 0:
coins_used.append(parent[current])
current -= parent[current]
return coins_used
# Canonical system: greedy works
us_coins = [25, 10, 5, 1]
print(f"US coins for 67¢: {greedy_coin_change(67, us_coins)}") # [25, 25, 10, 5, 1, 1]
# Non-canonical system: greedy fails
weird_coins = [1, 3, 4]
print(f"Greedy for 6¢: {greedy_coin_change(6, weird_coins)}") # [4, 1, 1] - 3 coins
print(f"DP for 6¢: {dp_coin_change(6, weird_coins)}") # [3, 3] - 2 coins
Classic Greedy Algorithms
Two algorithms showcase greedy thinking at its finest: interval scheduling and Huffman coding.
Interval scheduling solves the problem of selecting the maximum number of non-overlapping activities. The key insight is counterintuitive: sort by end time, not start time or duration. This ensures each choice leaves maximum room for future activities.
from dataclasses import dataclass
@dataclass
class Interval:
start: int
end: int
name: str = ""
def interval_scheduling(intervals: list[Interval]) -> list[Interval]:
"""
Select maximum number of non-overlapping intervals.
Greedy strategy: always pick the interval that ends earliest.
"""
if not intervals:
return []
# Sort by end time - this is the critical insight
sorted_intervals = sorted(intervals, key=lambda x: x.end)
selected = [sorted_intervals[0]]
last_end = sorted_intervals[0].end
for interval in sorted_intervals[1:]:
if interval.start >= last_end:
selected.append(interval)
last_end = interval.end
return selected
# Example: conference room scheduling
meetings = [
Interval(0, 6, "Long morning meeting"),
Interval(1, 4, "Team standup"),
Interval(3, 5, "Design review"),
Interval(5, 7, "Client call"),
Interval(3, 9, "All-hands"),
Interval(5, 9, "Training"),
Interval(6, 10, "Sprint planning"),
Interval(8, 11, "One-on-one"),
]
scheduled = interval_scheduling(meetings)
print(f"Maximum meetings: {len(scheduled)}")
for m in scheduled:
print(f" {m.start}-{m.end}: {m.name}")
Huffman coding builds optimal prefix-free codes for data compression. It repeatedly combines the two lowest-frequency symbols, building a tree from the bottom up.
import heapq
from dataclasses import dataclass, field
from typing import Optional
@dataclass(order=True)
class HuffmanNode:
freq: int
char: Optional[str] = field(compare=False, default=None)
left: Optional['HuffmanNode'] = field(compare=False, default=None)
right: Optional['HuffmanNode'] = field(compare=False, default=None)
def build_huffman_tree(frequencies: dict[str, int]) -> HuffmanNode:
"""
Build Huffman tree using a min-heap.
Greedy strategy: always combine the two lowest-frequency nodes.
"""
heap = [HuffmanNode(freq=freq, char=char)
for char, freq in frequencies.items()]
heapq.heapify(heap)
while len(heap) > 1:
left = heapq.heappop(heap)
right = heapq.heappop(heap)
merged = HuffmanNode(
freq=left.freq + right.freq,
left=left,
right=right
)
heapq.heappush(heap, merged)
return heap[0]
def generate_codes(node: HuffmanNode, prefix: str = "") -> dict[str, str]:
"""Generate Huffman codes by traversing the tree."""
if node.char is not None:
return {node.char: prefix or "0"}
codes = {}
if node.left:
codes.update(generate_codes(node.left, prefix + "0"))
if node.right:
codes.update(generate_codes(node.right, prefix + "1"))
return codes
# Example: compress "hello world"
text = "hello world"
frequencies = {}
for char in text:
frequencies[char] = frequencies.get(char, 0) + 1
tree = build_huffman_tree(frequencies)
codes = generate_codes(tree)
print("Huffman codes:")
for char, code in sorted(codes.items(), key=lambda x: len(x[1])):
print(f" '{char}': {code} (freq: {frequencies[char]})")
original_bits = len(text) * 8
compressed_bits = sum(len(codes[c]) * frequencies[c] for c in frequencies)
print(f"\nCompression: {original_bits} bits -> {compressed_bits} bits")
Graph Algorithms: MST and Shortest Paths
Graph algorithms provide some of the most elegant greedy solutions. Kruskal’s algorithm finds a minimum spanning tree by repeatedly adding the cheapest edge that doesn’t create a cycle.
class UnionFind:
"""Disjoint set data structure for cycle detection."""
def __init__(self, n: int):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x: int) -> int:
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x]) # Path compression
return self.parent[x]
def union(self, x: int, y: int) -> bool:
"""Returns True if union was performed (no cycle)."""
px, py = self.find(x), self.find(y)
if px == py:
return False # Cycle detected
# Union by rank
if self.rank[px] < self.rank[py]:
px, py = py, px
self.parent[py] = px
if self.rank[px] == self.rank[py]:
self.rank[px] += 1
return True
def kruskal_mst(n: int, edges: list[tuple[int, int, int]]) -> list[tuple[int, int, int]]:
"""
Find MST using Kruskal's algorithm.
edges: list of (u, v, weight)
Greedy strategy: always add the cheapest edge that doesn't create a cycle.
"""
edges = sorted(edges, key=lambda x: x[2])
uf = UnionFind(n)
mst = []
for u, v, weight in edges:
if uf.union(u, v):
mst.append((u, v, weight))
if len(mst) == n - 1:
break
return mst
# Example: network infrastructure
edges = [
(0, 1, 4), (0, 7, 8), (1, 2, 8), (1, 7, 11),
(2, 3, 7), (2, 8, 2), (2, 5, 4), (3, 4, 9),
(3, 5, 14), (4, 5, 10), (5, 6, 2), (6, 7, 1), (6, 8, 6), (7, 8, 7)
]
mst = kruskal_mst(9, edges)
total_weight = sum(w for _, _, w in mst)
print(f"MST edges: {mst}")
print(f"Total weight: {total_weight}")
Real-World Applications
Greedy algorithms power critical infrastructure across the tech industry.
Task scheduling uses interval scheduling variants for CI/CD pipelines, meeting room allocation, and cloud resource provisioning. When you schedule jobs with deadlines and profits, the greedy approach of sorting by deadline and using a disjoint set to find available slots runs in O(n log n).
Data compression relies on Huffman coding as a building block. Modern codecs like DEFLATE (used in gzip, PNG) combine Huffman coding with LZ77 for impressive compression ratios.
Network routing employs Dijkstra’s algorithm for shortest path calculations in OSPF routing protocols. CDN edge server selection uses greedy heuristics to minimize latency.
Resource budgeting often maps to the fractional knapsack problem, where you can take fractions of items. Unlike 0/1 knapsack, the greedy solution (sort by value-to-weight ratio) is provably optimal.
Common Pitfalls and Debugging
The most dangerous mistake is assuming greedy works without proof. Here’s a side-by-side comparison showing why the 0/1 knapsack problem defeats greedy approaches:
def greedy_knapsack(capacity: int, items: list[tuple[int, int]]) -> tuple[int, list[int]]:
"""
Greedy 0/1 knapsack - DOES NOT give optimal solution.
items: list of (weight, value)
Strategy: sort by value/weight ratio, take best items that fit.
"""
indexed_items = [(w, v, v/w, i) for i, (w, v) in enumerate(items)]
indexed_items.sort(key=lambda x: x[2], reverse=True)
total_value = 0
selected = []
remaining = capacity
for weight, value, ratio, idx in indexed_items:
if weight <= remaining:
selected.append(idx)
total_value += value
remaining -= weight
return total_value, selected
def dp_knapsack(capacity: int, items: list[tuple[int, int]]) -> tuple[int, list[int]]:
"""
Dynamic programming 0/1 knapsack - always optimal.
"""
n = len(items)
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
weight, value = items[i - 1]
for w in range(capacity + 1):
dp[i][w] = dp[i - 1][w]
if weight <= w:
dp[i][w] = max(dp[i][w], dp[i - 1][w - weight] + value)
# Reconstruct solution
selected = []
w = capacity
for i in range(n, 0, -1):
if dp[i][w] != dp[i - 1][w]:
selected.append(i - 1)
w -= items[i - 1][0]
return dp[n][capacity], selected[::-1]
# Counterexample where greedy fails
items = [(10, 60), (20, 100), (30, 120)] # (weight, value)
capacity = 50
greedy_val, greedy_items = greedy_knapsack(capacity, items)
dp_val, dp_items = dp_knapsack(capacity, items)
print(f"Greedy: value={greedy_val}, items={greedy_items}") # 180, [0, 2]
print(f"DP: value={dp_val}, items={dp_items}") # 220, [1, 2]
Performance Characteristics
Greedy algorithms typically run in O(n log n) time, dominated by sorting. Compare this to dynamic programming’s O(n × capacity) for knapsack or brute force’s O(2^n) for subset problems.
The trade-off is clear: greedy is fast but only works for specific problem structures. When correctness isn’t guaranteed, greedy algorithms still serve as excellent heuristics. A greedy approximation for the traveling salesman problem runs in polynomial time and typically produces solutions within 25% of optimal—often good enough for practical applications.
Use greedy as your first attempt. Prove correctness if you can. If you can’t prove it, test exhaustively with adversarial inputs. When greedy fails, reach for dynamic programming or branch-and-bound. But when greedy works, you get elegant, efficient solutions that are easy to implement and debug.