Greedy Algorithms Explained (With Python Examples)

A greedy algorithm builds a solution step by step, always taking the option that looks best right now, and never reconsidering. When it works, it is usually simple and fast. The hard part is knowing whether it works: for many problems the locally best choice leads to a worse overall result.

You have already met greedy algorithms: Dijkstra always finalises the closest vertex, and Kruskal and Prim always take the cheapest safe edge.

Activity selection#

Many meetings want the same room. Each has a start and end time. Fit in as many as possible.

Natural guesses fail: picking the shortest meeting, or the earliest start, can block several others. The choice that works: always pick the meeting that ends first among those that fit. Ending early leaves the most room for the rest.

def max_meetings(meetings):
    chosen = []
    last_end = float("-inf")
    for start, end in sorted(meetings, key=lambda m: m[1]):   # by end time
        if start >= last_end:
            chosen.append((start, end))
            last_end = end
    return chosen

meetings = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]
print(max_meetings(meetings))

[(1, 4), (5, 7), (8, 11), (12, 16)]

Sorting dominates the cost: O(n log n).

Why it is correct (an "exchange argument"): take any best schedule. Its first meeting ends no earlier than the meeting that ends first overall, so swapping them keeps the schedule valid and just as large. Repeat for the rest. Arguments like this are how greedy choices are justified.

Merging overlapping intervals#

Sort by start, then extend the current interval while the next one overlaps:

def merge_intervals(intervals):
    merged = []
    for start, end in sorted(intervals):
        if merged and start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])
    return merged

print(merge_intervals([[1, 3], [8, 10], [2, 6], [15, 18], [17, 20]]))

[[1, 6], [8, 10], [15, 20]]

Jump game#

Each number says how far you may jump forward from that position. Can you reach the last index? Track the furthest reachable index as you walk:

def can_reach_end(jumps):
    furthest = 0
    for i, jump in enumerate(jumps):
        if i > furthest:
            return False               # this index cannot be reached
        furthest = max(furthest, i + jump)
    return True

print(can_reach_end([2, 3, 1, 1, 4]))
print(can_reach_end([3, 2, 1, 0, 4]))

True
False

In the second list every route lands on the 0 at index 3 and gets stuck.

When greedy fails: coin change#

Make an amount with the fewest coins. Greedy says: always take the largest coin that fits. With Indian rupee coins and notes (1, 2, 5, 10, …) that happens to give the best answer, but with other coin systems it does not:

def greedy_coins(coins, amount):
    used = []
    for c in sorted(coins, reverse=True):
        while amount >= c:
            amount -= c
            used.append(c)
    return used if amount == 0 else None

def best_coins(coins, amount):               # dynamic programming, see the DP lessons
    best = [0] + [float("inf")] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                best[a] = min(best[a], best[a - c] + 1)
    return best[amount]

print(greedy_coins([1, 2, 5, 10], 18), best_coins([1, 2, 5, 10], 18))
print(greedy_coins([1, 3, 4], 6), best_coins([1, 3, 4], 6))

[10, 5, 2, 1] 4
[4, 1, 1] 2

For coins 4 and amount 6, greedy takes 4 + 1 + 1 (3 coins), but 3 + 3 needs only 2. When greedy has no exchange argument, use dynamic programming.

Greedy or dynamic programming?#

A good habit: when a greedy idea comes to mind, try hard to break it with a small counterexample before trusting it.

Common mistakes#

Practice#

def start_station(gas, cost):
    if sum(gas) < sum(cost):
        return -1
    start, tank = 0, 0
    for i in range(len(gas)):
        tank += gas[i] - cost[i]
        if tank < 0:
            start, tank = i + 1, 0
    return start

print(start_station([1, 2, 3, 4, 5], [3, 4, 5, 1, 2]))
print(start_station([2, 3, 4], [3, 4, 3]))

3
-1

Key takeaway#

Next: solving each subproblem once, with Dynamic Programming.