Greedy

Overview

A greedy algorithm builds a solution step by step, always taking the choice that looks best right now. When a problem has the "greedy choice property," these local decisions lead to a correct global answer. Greedy solutions are often simple and fast, but they only work when a local optimum truly leads to a global optimum.

Syntax / Usage

You usually sort or prioritize the options, then iterate once making the best immediate pick. Coin change with canonical denominations is a classic greedy example.

def make_change(amount, coins):          # greedy: works for canonical coin systems
    coins = sorted(coins, reverse=True)  # largest first
    result = []
    for coin in coins:
        while amount >= coin:
            amount -= coin
            result.append(coin)
    return result if amount == 0 else None

Examples

Greedily pick the largest coins first to reach an amount:

print(make_change(63, [1, 5, 10, 25]))  # [25, 25, 10, 1, 1, 1]

Select the most non-overlapping meetings by finishing earliest:

def max_meetings(intervals):             # O(n log n) due to sorting
    intervals.sort(key=lambda pair: pair[1])  # by end time
    count, end = 0, float("-inf")
    for start, finish in intervals:
        if start >= end:
            count += 1
            end = finish
    return count

print(max_meetings([(1, 3), (2, 4), (3, 5)]))  # 2

Common Mistakes

• Assuming greedy always works; some problems need dynamic programming instead.
• Using greedy coin change on non-canonical coins where it gives a suboptimal answer.
• Sorting by the wrong key, such as start time instead of finish time.
• Not proving the greedy choice property before trusting the result.
• Forgetting to handle the case where no valid solution exists.

See Also

algorithms-dynamic-programming algorithms-sorting algorithms-big-o-notation