The greedy leap

Because after sorting, conflicts can only be between neighbors, so one linear pass settles everything.

Sorting made the answer local. Each meeting only had to be compared with the next one, rather than with every other meeting in the list.

The reason that works is the ordering itself. Once meetings are sorted by start time, any meeting later in the list starts even later, so if the immediate neighbor does not conflict, nothing after it can either.

Greedy algorithms, this unit's topic, push that idea further. Sort, then make one irreversible choice per element and never look back.

The word irreversible is the interesting part. Backtracking undid its choices and greedy refuses to, which is what makes greedy fast and what makes it wrong when the rule is chosen carelessly.

The greedy leap

A greedy algorithm builds a solution by repeatedly taking the choice that looks best right now, and never undoing it. No recursion tree and no backtracking, usually just a sort plus one pass.

The classic example is maximum meetings. Given meetings with start and end times and a single room, how many can you host?

The greedy rule that works is to always take the meeting that ends earliest among those that fit.

The reasoning is what makes it credible. Whatever meeting you take, the only thing that affects the future is when the room frees up, so the earliest-ending compatible meeting frees the room soonest and leaves maximal space for the rest.

That style of justification has a name, the exchange argument. Take any optimal schedule, swap its first meeting for the earliest-ending one, and the schedule stays valid and just as large, so the greedy choice is never wrong.

Being able to produce that argument is the whole skill here. Greedy code is short enough to guess, and the proof is what distinguishes a correct rule from a plausible one.

Maximum meetings in one room

Sort by end time, then take any meeting that starts at or after the room frees up.

def max_meetings(meetings):
    meetings = sorted(meetings, key=lambda m: m[1])
    count = 0
    free_at = 0
    for start, end in meetings:
        if start >= free_at:
            count += 1
            free_at = end
    return count

schedule = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11)]
print(max_meetings(schedule))

Output

3

key=lambda m: m[1] sorts by end time, which is the entire greedy rule expressed as a sort. The pass afterwards has no choices left to make.

free_at is the only state carried forward, and it holds when the room becomes available. That single number is enough because nothing else about the accepted meetings affects future decisions.

start >= free_at allows a meeting to begin exactly when the previous one ends, which is the boundary convention from lesson 3-3 and worth confirming with an interviewer.

Tracing the accepted set: (1, 4) is taken and frees the room at 4, (3, 5) and (0, 6) both start too early, (5, 7) is taken and frees at 7, then (8, 11) is taken. That is 3.

The cost is O(n log n) for the sort plus O(n) for the pass, and the sort dominates. That is the usual shape of a greedy solution.

Because the meeting that ends earliest frees the room soonest, and only the room's free-up time affects future choices.

The exchange argument makes that precise. Swapping the earliest-ending meeting into any optimal schedule keeps it valid and the same size, so no optimal solution is lost by taking it.

Both alternatives fail on concrete inputs, which is the useful way to reject them.

Sorting by earliest start grabs (0, 6) from this lesson's schedule, which occupies the room until 6 and blocks both (1, 4) and (5, 7), trading two meetings for one.

Sorting by shortest duration fails on a case like (1, 5), (4, 6), (5, 9). The two-hour (4, 6) looks best and straddles the other two, giving 1 where the answer is 2.

Building a small counterexample is how you test any proposed greedy rule, and it is faster than trying to prove a wrong rule correct. Three intervals are usually enough.

make_change

US cashiers make change greedily, always handing over the biggest coin that fits.

def make_change(cents):
    used = []
    for coin in (25, 10, 5, 1):
        while cents >= coin:
            cents -= coin
            used.append(coin)
    return used

print(make_change(68))
print(make_change(41))

Output

[25, 25, 10, 5, 1, 1, 1]
[25, 10, 5, 1]

The structure is an outer loop over the coins from largest to smallest, with an inner while that keeps subtracting a coin as long as it fits.

The coin order is load-bearing. Listing the tuple as (1, 5, 10, 25) would spend the whole amount in pennies and never reach a quarter.

The while rather than an if is what allows repeats, which is how 68 uses two quarters and three pennies.

Checking the arithmetic: 68 = 25 + 25 + 10 + 5 + 1 + 1 + 1, seven coins, and 41 = 25 + 10 + 5 + 1, four coins. Both are the fewest possible.

For US coins greedy happens to be optimal, and that phrasing is deliberate. It is a property of this particular coin system rather than of the greedy strategy.

Hold on to this function, because the next lesson shows a coin system where this exact strategy gives a wrong answer.