ZERO / HERO
Always grab the nearest deadline

Greedy & the Exchange Argument

The analogy

Sometimes the obviously best-looking local choice really is globally optimal — pick the meeting that ends soonest and you fit the most meetings in. Sometimes it is a trap. The whole skill is knowing which situation you are in, and being able to argue it rather than hope.

Visualizer

Greedy vs optimal

step 1 / 8
coins usedtotal
Greedy—0
Optimal—0

Coins [1, 3, 4], make 6. Greedy takes the biggest coin that fits, repeatedly. Optimal is whatever actually minimises the count.coins [1,3,4], target 6

def max_meetings(intervals):
    # sort by EARLIEST FINISH — this key is the algorithm
    intervals.sort(key=lambda x: x[1])
    count, last_end = 0, float("-inf")
    for start, end in intervals:
        if start >= last_end:
            count += 1
            last_end = end
    return count

# greedy FAILS for coin change with arbitrary coins:
#   coins = [1, 3, 4], target = 6
#   greedy -> 4 + 1 + 1 = 3 coins
#   optimal -> 3 + 3     = 2 coins
# => needs DP

import heapq                       # greedy + heap: scheduling
def min_rooms(intervals):
    intervals.sort()
    ends = []
    for s, e in intervals:
        if ends and ends[0] <= s:
            heapq.heappop(ends)
        heapq.heappush(ends, e)
    return len(ends)
Check yourself

Interval scheduling: which sort key is provably optimal?