Greedy Algorithms

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

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.

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.

def max_profit(prices):
    return sum(max(0, b - a) for a, b in zip(prices, prices[1:]))

print(max_profit([7, 1, 5, 3, 6, 4]))   # 7