Algorithms · Lesson 4 of 6

Greedy Algorithms

Make the locally best choice at each step, and know when that is enough.

• Intermediate
• 14 min read
• 3 objectives

Before this lessonLesson 3: Recursion

A greedy algorithm builds a solution one step at a time, always taking the choice that looks best right now, and never reconsidering. When it works, greedy is wonderfully simple and fast. The catch is that it works only for problems with the greedy choice property: a locally best choice can always be extended to a globally best solution.

Always take the best-looking option right now

A greedy algorithm builds a solution one step at a time, and at each step picks whatever looks best at that moment, never reconsidering. When it works, greedy is wonderfully simple and fast. When it does not, it gives confident wrong answers, so the real skill is knowing when it is safe. Making change with coins is the standard example.

Example: making change

With standard coins, always take the largest coin that fits.

def make_change(amount, coins=(25, 10, 5, 1)):
    result = []
    for c in coins:
        while amount >= c:
            amount -= c
            result.append(c)
    return result

print(make_change(63))

[25, 25, 10, 1, 1, 1]

Interval scheduling

Given meetings with start and end times, attend as many as possible. The winning rule: always pick the meeting that ends earliest among those that do not overlap, because that 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]):
        if start >= last_end:
            chosen.append((start, end))
            last_end = end
    return chosen

print(max_meetings([(1, 4), (3, 5), (0, 6), (5, 7), (8, 9), (5, 9)]))

[(1, 4), (5, 7), (8, 9)]

Jump game

Each number says how far you may jump. Can you reach the end? Track the farthest index reachable so far.

def can_reach_end(nums):
    farthest = 0
    for i, jump in enumerate(nums):
        if i > farthest:
            return False
        farthest = max(farthest, i + jump)
    return True

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

True False

How to justify a greedy choice

• Exchange argument: show that any optimal solution can be transformed to use your greedy choice without getting worse.
• Stays ahead: show that after each step greedy is at least as good as any other strategy.

Famous greedy algorithms you will meet later include Dijkstra's shortest paths, Kruskal's and Prim's minimum spanning trees and Huffman coding.

Making change: greedy works here

def make_change(amount, coins=(25, 10, 5, 1)):
    used = []
    for coin in coins:              # largest first
        while amount >= coin:
            amount -= coin
            used.append(coin)
    return used

print(make_change(63))

[25, 25, 10, 1, 1, 1]

...and greedy fails here

With coins 1, 3 and 4, making 6 greedily takes 4 + 1 + 1 (three coins), but the best answer is 3 + 3 (two coins). Greedy is only correct when the coin system has a special structure. This is why you must be able to justify a greedy choice, not just hope.

def greedy(amount, coins):
    used = []
    for c in sorted(coins, reverse=True):
        while amount >= c:
            amount -= c
            used.append(c)
    return used

print(greedy(6, [1, 3, 4]))     # greedy: 3 coins
print([3, 3])                   # optimal: 2 coins

[4, 1, 1]
[3, 3]

Interval scheduling: a greedy that is provably correct

To fit the most meetings in one room, always pick the meeting that ends earliest. It leaves the most room for the rest, and this can be proven optimal.

meetings = [(1, 4), (3, 5), (0, 6), (5, 7), (8, 9), (5, 9)]
chosen, last_end = [], 0
for start, end in sorted(meetings, key=lambda m: m[1]):
    if start >= last_end:
        chosen.append((start, end))
        last_end = end
print(chosen)

[(1, 4), (5, 7), (8, 9)]

Key takeaways

• Greedy picks the locally best choice each step and never looks back.
• It is fast and simple but only correct for problems with the right structure.
• Sort first, then sweep; and always try to find a counterexample before trusting a greedy rule.

# Write your solution here