Greedy — Take the Best Option Now

What is it? #

A greedy algorithm makes the choice that looks best right now and never reconsiders.

That makes it fast and simple. The hard part is not writing it — it is knowing whether it gives the correct answer for your problem.

For some problems greedy is provably optimal. Scheduling the most meetings in a room, building a minimum spanning tree, and making change with well-designed coin systems all work.

For others it produces a decent answer that is not the best one. Knowing the difference is the whole skill, and when greedy fails, dynamic programming is usually the next tool.

Think of it like this #

Walking to the highest point in a hilly area by always stepping uphill. You will certainly reach a peak — but perhaps a small one, with the real summit visible across a valley you refused to cross.

Sometimes always going up works, because the landscape has one peak. Recognising which landscape you are in is the entire question.

Simple example #

You have meeting requests and one room. You want to fit in as many meetings as possible. Sorting by earliest finish time and greedily taking each compatible meeting is provably optimal. Then the coin change example shows the same approach giving the wrong answer.

Code #

# Greedy that works: maximise the number of non-overlapping meetings
def max_meetings(meetings):
    """meetings: list of (start, end)."""
    chosen = []
    for start, end in sorted(meetings, key=lambda m: m[1]):   # earliest finish
        if not chosen or start >= chosen[-1][1]:
            chosen.append((start, end))
    return chosen


requests = [(9, 11), (10, 12), (11, 13), (12, 14), (9, 17)]
print(max_meetings(requests))      # [(9, 11), (11, 13), (12, 14)] -> 3 meetings


# Greedy that works: fewest coins with a well-designed system
def change_greedy(amount, coins=(500, 100, 50, 20, 10, 5, 2, 1)):
    result = []
    for coin in coins:
        while amount >= coin:
            amount -= coin
            result.append(coin)
    return result

print(change_greedy(287))          # [100, 100, 50, 20, 10, 5, 2]


# Greedy that FAILS on an unusual coin system
print(change_greedy(6, coins=(4, 3, 1)))   # [4, 1, 1] -> 3 coins
# The optimal answer is [3, 3] -> 2 coins.
# Greedy took the 4 and could not recover.


# Correct answer for any coin system: dynamic programming
def change_dp(amount, coins):
    best = [0] + [float("inf")] * amount
    for value in range(1, amount + 1):
        for coin in coins:
            if coin <= value:
                best[value] = min(best[value], best[value - coin] + 1)
    return best[amount]

print(change_dp(6, (4, 3, 1)))     # 2


# Greedy on a knapsack by value density — an approximation, not optimal
def fractional_knapsack(capacity, items):
    """items: list of (value, weight). Fractions allowed -> greedy IS optimal."""
    total = 0.0
    for value, weight in sorted(items, key=lambda i: i[0] / i[1], reverse=True):
        take = min(weight, capacity)
        total += value * (take / weight)
        capacity -= take
        if capacity == 0:
            break
    return total

print(fractional_knapsack(10, [(60, 10), (100, 20), (120, 30)]))   # 60.0

How it works #

max_meetings sorts by finish time, not start time or duration. That choice is what makes it correct: taking the meeting that frees the room earliest always leaves the most room for what follows. This can be proved with an exchange argument — any optimal schedule can be rewritten to start with the earliest-finishing meeting without getting worse.

change_greedy takes the largest coin that fits, repeatedly. With standard currency denominations this gives the fewest coins, because each denomination is at least twice the next.

The failing case shows why that is not a general rule. With coins of 4, 3 and 1, greedily taking the 4 leaves 2, which needs two 1s — three coins total. Two 3s would have been better. The greedy choice was locally sensible and globally wrong.

change_dp builds up answers for every amount from 1 upwards, so it can consider combinations greedy never reaches. It is slower but always correct.

fractional_knapsack is greedy and optimal because fractions are allowed: taking the highest value per unit weight can never be improved. Remove the fractions — the 0/1 knapsack — and greedy breaks again, because you cannot fill the last gap partially.

The pattern is consistent: greedy works when a local choice provably cannot block a better global outcome. When it can, you need DP or search.

Real-world use #

Greedy algorithms run in real systems constantly because they are fast and often good enough. Task schedulers pick the shortest or highest-priority job. Load balancers send requests to the least-busy server. Caches evict the least recently used entry.

Huffman coding, used in compression formats, is greedy: repeatedly merge the two least frequent symbols. It is provably optimal for that problem.

Network routing protocols use greedy steps over local information, and Dijkstra's algorithm is itself greedy — always expand the nearest unvisited node, which is safe when weights are non-negative.

In business logic, greedy is often chosen deliberately: an approximate answer computed in milliseconds beats a perfect answer that takes a minute. The important thing is knowing that you made that trade-off rather than assuming the answer is optimal.

Common mistakes #

• Assuming greedy is optimal without checking. Test it against a brute-force answer on small inputs.
• Sorting by the wrong criterion — meetings by start time instead of finish time gives a worse schedule.
• Using greedy for 0/1 knapsack, where it does not work.
• Treating a good-enough approximation as exact in a context where exactness matters, such as billing.
• Reaching for dynamic programming first when a proven greedy solution exists and is far simpler.

Practice #

Given a list of activities with start and end times, return the maximum number that fit in one room. Then write a brute-force version that tries all subsets, and compare results on random small inputs to confirm the greedy answer matches. Finally, find a coin system where greedy change fails and explain why.