Greedy Algorithms

What we are trying to do

An algorithm is a fixed set of steps for solving a problem. A greedy algorithm is a particular style of algorithm: at each step it makes the choice that looks best right now, without looking ahead and without ever undoing a choice it already made. “Greedy” is meant literally. The algorithm grabs the most attractive option in front of it and commits.

That sounds naive, and sometimes it is. But for certain problems this shortsighted strategy happens to produce the best possible overall answer, and when it works it is both simple to write and fast to run. The whole difficulty of this topic is not writing greedy code. It is knowing which problems greedy actually solves correctly, because on the wrong problem it produces a confident, wrong answer with no warning.

This lesson covers three things: what makes a problem greedy-friendly, one problem where greedy is provably correct (interval scheduling), and one problem where greedy quietly fails (a certain coin system). By the end you should be suspicious of any greedy solution that has not been justified.

Two terms up front:

• Optimal means “the best possible” by whatever measure the problem cares about (the most items, the fewest coins, the shortest distance). An optimal solution is one you cannot beat.
• A candidate is one of the choices available at the current step. Greedy ranks the candidates by some rule and takes the top one.

The shape of every greedy algorithm

Strip away the specific problem and every greedy algorithm has the same three parts.

1. A rule for ordering the candidates from most to least attractive (often achieved by sorting, arranging items by some key).
2. A loop that walks the candidates in that order.
3. Inside the loop, a test: is it still valid to take this candidate? If yes, take it and never reconsider. If no, skip it.

Those three parts wire together into a single loop, one committed choice per pass:

flowchart TD
    A["Sort candidates by the greedy rule"] --> B["Look at next candidate"]
    B --> C{"Is it still valid<br/>to take it?"}
    C -->|yes| D["Take it. Never undo."]
    C -->|no| E["Skip it."]
    D --> F{"Any candidates left?"}
    E --> F
    F -->|yes| B
    F -->|no| G["Done. Return what we took."]

Notice what is missing compared to other strategies: there is no backtracking (undoing a choice and trying another), and no exploring several futures to compare them. One pass, one committed choice per step. That is why greedy is fast. It is also exactly why it can be wrong: a choice that looks best locally can block a better global outcome, and greedy never goes back to fix it.

When greedy is correct: the greedy-choice property

A greedy algorithm gives the optimal answer only when the problem has the greedy-choice property: there is always some optimal solution that includes the locally-best choice. Put plainly, taking the top-ranked candidate right now never costs you the ability to finish optimally. If that holds at every step, then a chain of locally-best choices assembles into a globally-best answer.

The honest situation for a beginner is this: you cannot tell by looking whether a problem has this property. You have to either prove it or test it hard. The rest of the lesson shows one problem where it holds and one where it does not, so you can feel the difference.

A problem where greedy works: interval scheduling

Here is the problem. You have a list of activities, each with a start time and an end time. Only one activity can run at a time (think of one room, one machine, one person). Two activities conflict if their time ranges overlap. Goal: choose the largest number of activities you can do without any two conflicting.

Say the activities are these, labeled A through F, each written as (start, end):

The greedy rule that works here is: always take the activity that finishes earliest among those that do not conflict with what you have already taken. The intuition is that finishing early leaves the most remaining time for everything else, so an early-finishing activity is the least “expensive” one to commit to.

Here is the key move: sort the activities by end time. Then walk the list once, keeping a running value last_end (the finish time of the most recently accepted activity). Accept an activity only if its start is not before last_end.

def max_activities(activities):
    # activities: list of (start, end) pairs
    ordered = sorted(activities, key=lambda a: a[1])  # sort by end time
    chosen = []
    last_end = float("-inf")   # "negative infinity": smaller than any real time
    for start, end in ordered:
        if start >= last_end:  # no overlap with the last one we took
            chosen.append((start, end))
            last_end = end
    return chosen

acts = [(1, 3), (2, 5), (4, 7), (1, 8), (5, 9), (8, 10)]
print(max_activities(acts))
# -> [(1, 3), (4, 7), (8, 10)]

A few terms in that code. sorted(..., key=lambda a: a[1]) returns a new list ordered by each pair’s second element, the end time; lambda a: a[1] is a tiny throwaway function that, given a pair a, returns a[1]. float("-inf") is a value guaranteed to be smaller than any real start time, so the very first activity is always accepted. start >= last_end is the no-conflict test: the new activity may begin exactly when the last one ended.

Tracing it step by step

Sorted by end time, the order is A(1,3), B(2,5), C(4,7), D(1,8), E(5,9), F(8,10). We walk that order and track last_end and the chosen set.

The answer is three activities: A, C, F. You can check by hand that no selection of four is possible here, so greedy found the optimum.

Why this greedy rule is correct: the exchange argument

An exchange argument is the standard way to prove a greedy choice is safe. The shape of the argument: take any optimal solution, and show you can swap in the greedy choice without making the solution worse. If the greedy choice can always replace the corresponding piece of some optimum, then greedy is never wrong.

Apply it here. Let the greedy algorithm’s first pick be the activity that finishes earliest; call it g. Now take any optimal schedule and look at its first activity (the one that starts earliest in that optimal set); call it o. Two cases:

• If o is g, they already agree on the first choice.
• If o is not g, then because g finishes earliest of everything, g finishes no later than o. So we can remove o from the optimal schedule and drop g in its place. Everything that came after o started after o ended, which is at or after when g ends, so nothing now conflicts. The schedule still has the same number of activities, so it is still optimal, and now it starts with g.

Either way, some optimal solution begins with the greedy choice. Remove g and the time it occupies, and the remaining problem is a smaller version of the same problem. Repeat the argument on it. Choice by choice, greedy stays inside an optimal solution the whole way. That is the greedy-choice property, proven.

The reason this is worth doing: the proof is what separates “greedy that works” from “greedy that happens to pass my three test cases.” Without it you are guessing.

A problem where greedy fails: coin change

Now a problem that looks just as greedy-friendly but is not. You want to make a target amount of money using the fewest coins, drawing from an unlimited supply of a few fixed denominations (the coin values available). The obvious greedy rule: repeatedly take the largest coin that does not overshoot the remaining amount.

def greedy_coins(amount, coins):
    coins = sorted(coins, reverse=True)  # largest first
    used = []
    for coin in coins:
        while amount >= coin:
            used.append(coin)
            amount -= coin
    return used

print(greedy_coins(63, [25, 10, 5, 1]))  # -> [25, 25, 10, 1, 1, 1]

On the everyday U.S.-style system [25, 10, 5, 1], greedy is actually optimal for every amount. Six coins for 63 cents is genuinely the best you can do. This is exactly the trap: greedy works here, so it feels like a general method.

Now change the coin system to [1, 3, 4] and ask for the amount 6.

print(greedy_coins(6, [4, 3, 1]))  # -> [4, 1, 1]   (three coins)

Greedy grabs the 4 first because it is the largest that fits, leaving 2, which it can only make as 1 + 1. Total: three coins. But 3 + 3 makes 6 with two coins. Greedy missed it, and it missed it precisely because it committed to the 4 and never reconsidered. The locally-best first move (the biggest coin) blocked the globally-best answer. Follow the two first moves from 6 and they end in different places:

flowchart TD
    A["Make 6 with coins {1, 3, 4}"] --> B["Greedy: take 4<br/>remaining 2"]
    A --> C["Better: take 3<br/>remaining 3"]
    B --> D["take 1, remaining 1"]
    D --> E["take 1, remaining 0<br/>THREE coins"]
    C --> F["take 3, remaining 0<br/>TWO coins"]

Why does the exchange argument fail here? Try to run it: claim the largest coin is always in some optimal solution. For amount 6 with {1,3,4}, the optimal solution is {3, 3}, which contains no 4 at all. The swap step breaks. The greedy-choice property simply does not hold for this coin system, and there is no way to patch the greedy rule to fix it. (The correct tool for general coin systems is dynamic programming, which does reconsider combinations. That is a separate topic.)

The lesson to carry away: greedy correctness depends on the exact inputs, not just the problem’s wording. Same “make change with fewest coins” problem, one coin set where greedy is optimal and one where it is not.

Complexity

For interval scheduling, the cost is dominated by the sort.

• Sorting n activities by end time costs O(n log n) time. Here n is the number of activities, and O(n log n) is the standard cost of a general comparison sort.
• The single pass afterward looks at each activity once and does a constant amount of work per activity: O(n) time.
• Total: O(n log n) + O(n), which simplifies to O(n log n) time, sort-dominated. This is typical of greedy algorithms. The greedy pass itself is cheap; the ordering step sets the cost.
• Space: O(n) to hold the sorted copy and the chosen list. If you sort the input in place and count only the output, the extra space can be as low as O(1) beyond the result.

For greedy coin change, sorting the (usually tiny) set of denominations is negligible; the loop runs at most amount / smallest_coin times, so it is fast. Coin change’s problem was never its speed; it was its correctness.

The general pattern: greedy trades away the guarantee of correctness for speed. Where it is valid, it is often the fastest correct method available, usually O(n log n) or better.

Common pitfalls

• Assuming greedy works without proof. This is the central danger of the whole topic. A greedy solution that passes a handful of examples can still be wrong on the next input, as the {1,3,4} coins show. Either prove the greedy-choice property (an exchange argument) or do not trust the greedy answer.
• Sorting by the wrong key. Interval scheduling is correct when you sort by end time. Sort by start time, or by shortest duration, and you get provably wrong answers on some inputs. The choice of ordering rule is the whole algorithm; a plausible-sounding rule is not automatically the right one.
• Confusing “greedy is fast” with “greedy is right.” Speed is never the question with greedy. Correctness is. A fast wrong answer is still wrong.
• Forgetting the equality case in the conflict test. Using start > last_end instead of start >= last_end would reject an activity that starts exactly when the previous one ends, even though those do not overlap. Decide deliberately whether touching endpoints count as a conflict.
• Assuming what works on one input set works on all of them. Greedy coin change is optimal on [25,10,5,1] and wrong on [1,3,4]. The problem statement is identical; only the data changed.

Practice

1. Modify max_activities to instead sort by start time and run it on [(1, 10), (2, 3), (4, 5)]. It should return only one activity. Explain in a sentence why sorting by start time can fail while sorting by end time does not.
2. Write a function that, given a coin system and a target amount, returns True if greedy uses the fewest possible coins for that amount and False otherwise, by comparing greedy’s count against a brute-force best over all combinations. Run it across amounts 1 through 30 for the coin set [1, 3, 4] and print every amount where greedy is not optimal.
3. You are given jobs each with a deadline and a fixed one-unit duration, and you want to schedule as many as possible before their deadlines. Propose a greedy ordering rule, then try to break it with a small input. If you cannot break it, sketch an exchange argument for why it holds.