Greedy Algorithms

A greedy algorithm makes the locally optimal choice at each step, hoping it leads to a globally optimal solution. Unlike Dynamic Programming, it never reconsiders past choices.

Why It Matters

Greedy algorithms are simple and fast. When they work, they’re the best approach. The challenge is proving they produce the correct answer — greedy doesn’t always work.

When Greedy Works

Greedy works when the problem has:

1. Greedy choice property — a locally optimal choice is part of a globally optimal solution
2. Optimal substructure — an optimal solution contains optimal solutions to subproblems

Classic Examples

Activity Selection (Interval Scheduling)

Pick the maximum number of non-overlapping activities. Greedy: always pick the activity that ends earliest.

def max_activities(intervals: list[tuple[int, int]]) -> list[tuple[int, int]]:
    """Select maximum non-overlapping intervals."""
    sorted_intervals = sorted(intervals, key=lambda x: x[1])  # sort by end time
    result = [sorted_intervals[0]]
    for start, end in sorted_intervals[1:]:
        if start >= result[-1][1]:  # no overlap with last selected
            result.append((start, end))
    return result
 
activities = [(1,3), (2,5), (3,6), (5,7), (8,9)]
assert max_activities(activities) == [(1,3), (5,7), (8,9)]

Fractional Knapsack

Take items by value-to-weight ratio. (Note: 0/1 knapsack requires Dynamic Programming.)

def fractional_knapsack(items: list[tuple[int,int]], capacity: int) -> float:
    """items = [(value, weight), ...]. Returns max value."""
    # Sort by value/weight ratio descending
    items = sorted(items, key=lambda x: x[0]/x[1], reverse=True)
    total = 0.0
    for value, weight in items:
        if capacity >= weight:
            total += value
            capacity -= weight
        else:
            total += value * (capacity / weight)
            break
    return total
 
assert fractional_knapsack([(60,10), (100,20), (120,30)], 50) == 240.0

Coin Change (Greedy — only works with certain coin sets)

def coin_change_greedy(coins: list[int], amount: int) -> list[int]:
    """Works for standard coin sets like [1, 5, 10, 25]."""
    coins = sorted(coins, reverse=True)
    result = []
    for coin in coins:
        while amount >= coin:
            result.append(coin)
            amount -= coin
    return result if amount == 0 else []  # empty if impossible
 
assert coin_change_greedy([1, 5, 10, 25], 41) == [25, 10, 5, 1]
# WARNING: fails for [1, 3, 4] amount=6: greedy gives [4,1,1], optimal is [3,3]

Greedy vs DP

	Greedy	DP
Approach	Choose locally optimal	Explore all subproblems
Speed	Usually O(n log n)	Usually O(n^2) or worse
Correctness	Must prove it works	Always finds optimal
When to use	Has greedy choice property	When greedy doesn’t work

Common Greedy Problems

• Interval scheduling / meeting rooms
• Huffman coding (compression)
• Dijkstra’s shortest path (greedy on min-heap)
• Minimum spanning tree (Kruskal’s, Prim’s)
• Job scheduling with deadlines

Related

• Dynamic Programming — use when greedy doesn’t guarantee optimality
• Sorting Algorithms — greedy often starts by sorting
• Heaps — greedy algorithms often use heaps
• Big O Notation — greedy is typically efficient