22. Greedy

What you'll learn

• 1Solve the activity selection / meeting room problem
• 2Solve coin change with canonical coin systems
• 3Use the exchange argument to prove greedy correctness

Overview

A greedy approach makes the choice that looks best right now without regard for future consequences. It's the simplest paradigm — when it works.

Core Concepts

1. Activity selection (meeting rooms)

def max_activities(intervals):
    # Sort by end time — greedy pick earliest-ending
    intervals.sort(key=lambda x: x[1])
    end = -float('inf')
    count = 0
    for s, e in intervals:
        if s >= end:
            count += 1
            end = e
    return count

Proof intuition: picking the earliest-ending activity leaves the most room for future activities.

2. Coin change (with canonical coin systems)

def coin_change_greedy(coins, target):
    """Works for canonical systems like Korean Won, USD.
       Does NOT work for arbitrary coins — use DP then."""
    coins.sort(reverse=True)
    count = 0
    for c in coins:
        count += target // c
        target %= c
    return count if target == 0 else -1

3. Fractional knapsack (vs 0/1)

def fractional_knapsack(items, capacity):
    """Items can be taken in fractions. Greedy works here, unlike 0/1."""
    items.sort(key=lambda iw: -iw[1] / iw[0])   # value/weight desc
    total = 0
    for w, v in items:
        if capacity >= w:
            total += v; capacity -= w
        else:
            total += v * (capacity / w); break
    return total

4. Proving greedy is correct

Exchange argument: assume there's an optimal solution that doesn't include the greedy choice. Swap one element with the greedy choice — show the solution remains at least as good. This gives a contradiction.

Examples

Example 1 — src/01_meeting_room.py

Maximum non-overlapping intervals.

Example 2 — src/02_coin_change.py

Greedy for Korean Won.

Example 3 — src/03_fractional_knapsack.py

Fractional knapsack — greedy works.

Example 4 — src/04_counterexample.py

Show that greedy fails for coins {1, 3, 4} when target is 6.

Common Mistakes

1. Applying greedy where DP is needed (0/1 knapsack, arbitrary-coin change).
2. Sorting by the wrong criterion — meeting rooms must sort by END, not start.
3. Skipping the proof — always sanity-check with a small example.
4. Forgetting strictness in comparisons (≥ vs >).

Recap

• Greedy = sort by the right key, then sweep.
• Proof: exchange argument or 'no-regret' reasoning.
• Not all problems admit greedy — check with examples first.

Try It

1. BOJ 1931 (Meeting rooms).
2. BOJ 11399 (ATM withdrawal time).
3. BOJ 11047 (Coin 0 — Korean Won).