Greedy Algorithms

Take the best choice right now

A greedy algorithm builds the answer step by step, always taking the choice that looks best at this moment, and never going back.

Think of it like this: Paying ₹87 with the fewest coins and notes: take the biggest that fits (₹50), then again (₹20, ₹10, ₹5, ₹2), until nothing is left.

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

print(fewest_coins(87, [1, 2, 5, 10, 20, 50]))

Output

[50, 20, 10, 5, 2]

Activity selection

You have many talks, each with a start and end time, and one room. How many can you fit without overlaps? Greedy rule: always pick the talk that ends earliest – it leaves the most time for the rest.

talks = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11)]
talks.sort(key=lambda t: t[1])          # by end time
chosen = []
free_at = 0
for start, end in talks:
    if start >= free_at:
        chosen.append((start, end))
        free_at = end
print(chosen)

Output

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

Greedy doesn't always work

With coins 1, 3 and 4, greedy pays 6 as 4 + 1 + 1 (three coins), but 3 + 3 is only two:

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

print(fewest_coins(6, [1, 3, 4]))

Output

[4, 1, 1]

Remember: Greedy is fast and simple, but you must be sure the “best right now” choice never ruins the final answer. When it might, use dynamic programming (Module 17) instead.