Greedy

Local optimum → global optimum?

A greedy algorithm commits to the locally best move (largest coin, earliest finishing meeting) and moves on. It only gives the right answer when the problem has the greedy-choice property — you must prove or test that.

Interval scheduling

To fit the most non-overlapping intervals, always take the one that finishes earliest.

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

Quick check: Coins [1, 3, 4], make 6 with fewest coins. Greedy (take 4 first) gives 3 coins (4+1+1). Optimal is...

• 3 coins — greedy is right
• 2 coins (3 + 3)
• Impossible