Greedy algorithms: the idea

What "greedy" means

A greedy algorithm makes one choice at a time, always taking the option that looks best at that moment (the most valuable, the cheapest, the earliest to finish), and never undoes a choice. Because it never looks back, it is usually just a sort plus one pass: O(n log n) time.

The catch: a locally best step does not always lead to the best overall answer. So with greedy there are always two questions: what is the greedy rule, and why is it correct? In interviews, giving a short reason, or a counterexample for a wrong rule, matters as much as the code.

When greedy works

• Greedy-choice property: there is always an optimal answer that includes the greedy first choice. So taking it never hurts.
• Optimal substructure: after the greedy choice, what is left is a smaller problem of the same kind, and an optimal answer to it, plus the first choice, is optimal overall.

The usual way to argue the first point is an exchange argument. Take ANY optimal answer. If it does not use the greedy choice, swap one of its choices for the greedy one and show the answer is still valid and no worse. Then an optimal answer with the greedy choice exists.

Example 1: the most meetings in one room

A single meeting room gets requests (start, end). Choose the largest number of meetings that do not overlap; a meeting may start exactly when the previous one ends. This is the activity selection problem. The greedy rule: sort by END time, and take each meeting that starts at or after the end of the last one taken.

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

print(max_meetings([(1, 4), (3, 5), (0, 6), (5, 7), (8, 9), (5, 9)]))   # Output: 3

Why the earliest end? Exchange argument: let the meeting that ends first be g. Any optimal schedule has some first meeting f. Since g ends no later than f, replace f with g: g still ends before the second meeting starts, so nothing overlaps and the count is the same. Taking g is therefore safe, and the rest is the same problem on the meetings that start after g ends.

Other rules that sound sensible are wrong. "Earliest start first" can pick one long meeting (0, 10) and block (1, 2), (3, 4) and (5, 6). "Shortest first" picks (4, 7) from (1, 5), (4, 7), (6, 10) and blocks both others, which fit together.

Example 2: change with Indian notes and coins

To pay an amount with the fewest notes and coins of ₹1, 2, 5, 10, 20, 50, 100, 200 and 500, take the largest denomination that fits, again and again. ₹1,388 becomes 500 + 500 + 200 + 100 + 50 + 20 + 10 + 5 + 2 + 1: ten pieces. For this set the greedy answer is always the minimum, because each denomination relates well to the smaller ones (systems like this are called canonical). ATMs and cash counters follow the same idea, limited by what notes they hold.

NOTES = [500, 200, 100, 50, 20, 10, 5, 2, 1]

def make_change(amount):
    used = []
    for note in NOTES:
        while amount >= note:
            amount -= note
            used.append(note)
    return used

print(make_change(1388))   # Output: [500, 500, 200, 100, 50, 20, 10, 5, 2, 1]

Where greedy fails: coins {1, 3, 4}

Now use coins of 1, 3 and 4 to make 6. Greedy takes 4, then 1, then 1: three coins. The best answer is 3 + 3: two coins. Taking the biggest coin first was a trap. With coins {5, 10} and amount 3, greedy gets stuck, and so does every method, because 3 cannot be made at all. For coin systems that are not canonical you need dynamic programming (Module 11), which tries every last coin and builds up answers for all smaller amounts.

Common mistakes

• Using greedy because it "feels right" without a reason. Fix: give an exchange argument or test small cases against brute force.
• Sorting meetings by start time or by length. Fix: sort by end time for maximum non-overlapping meetings.
• Getting the touching rule wrong: if back-to-back meetings are allowed, use start >= last_end; if not, use start > last_end. Ask.
• Assuming greedy change works for any coin system. Fix: it is correct for systems like Indian or US currency, not for {1, 3, 4}; use DP otherwise.
• Forgetting to sort a copy when the caller still needs the original order. Fix: sorted(items, key=...) returns a new list.