Greedy algorithms: interval scheduling and when greedy fails

A greedy algorithm builds an answer by taking the choice that looks best right now and never looking back. It is usually short and fast, often after one sort. The catch: it is only correct when the problem has the right structure. Interviews love greedy questions because the code is easy and the proof is the hard part. The code and output below were run with Python 3 before publishing.

Example 1: interval scheduling (greedy works)

You have meetings with start and end times and one room. What is the largest number of meetings you can attend with no overlaps?

The greedy rule that works: sort by end time and always take the meeting that ends first among those that fit. Finishing early leaves the most room for the rest. Sorting by start time or by shortest length looks tempting and is wrong.

Example 2: coin change (greedy fails)

"Always take the largest coin that fits" works for coins [25, 10, 5, 1], but not for [4, 3, 1] and an amount of 6. Greedy takes 4 + 1 + 1 = three coins, while 3 + 3 = two coins is better. When greedy is wrong, you need dynamic programming.

Example 3: jump game

You are given how far you can jump from each index. Can you reach the last index? Track the farthest index reachable so far. If you land on an index beyond it, you are stuck.

Code

def max_activities(intervals):
    """Most non-overlapping intervals: sort by end time, take whatever fits."""
    chosen, last_end = [], float("-inf")
    for start, end in sorted(intervals, key=lambda x: x[1]):
        if start >= last_end:
            chosen.append((start, end))
            last_end = end
    return chosen

def greedy_coins(coins, amount):
    count = 0
    for c in sorted(coins, reverse=True):
        count += amount // c
        amount %= c
    return count if amount == 0 else None

def best_coins(coins, amount):          # dynamic programming, for comparison
    INF = float("inf")
    dp = [0] + [INF] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and dp[a - c] + 1 < dp[a]:
                dp[a] = dp[a - c] + 1
    return dp[amount] if dp[amount] != INF else None

def can_jump(nums):                      # can you reach the last index?
    reach = 0
    for i, step in enumerate(nums):
        if i > reach:
            return False
        reach = max(reach, i + step)
    return True

Real output

activities: [(1, 4), (5, 7), (8, 11), (12, 16)]
coins [25,10,5,1], 63: greedy 6 best 6
coins [4,3,1], 6: greedy 3 best 2
jump [2,3,1,1,4]: True | [3,2,1,0,4]: False
activity selection matches brute force on 500 random cases

Here greedy found four meetings, (1, 4), (5, 7), (8, 11) and (12, 16). The interval-scheduling function was also compared with a brute-force check of every subset on 500 random cases, and they always agreed. The coin example shows the failure: greedy used 3 coins for 6 where the best is 2, so the DP version is needed.

How to tell if greedy is safe

1. Greedy-choice property. Can you argue that some optimal answer starts with your greedy choice?
2. Exchange argument. Take any optimal answer and swap in your greedy choice. If it never gets worse, greedy is safe.
3. Test against brute force on small random inputs, as above. If you find one counterexample, drop greedy.

Common mistakes

• Picking a plausible rule without a proof or a counterexample search.
• Sorting by the wrong key, such as start time instead of end time for scheduling.
• Using greedy on coin change with arbitrary coin values.
• Treating "it passed the examples" as proof.
• Forgetting the cost of the sort: O(n log n).

Main idea: greedy picks the locally best option and is only right when you can justify it. Sort by the right key, test against brute force, and fall back to dynamic programming when a counterexample appears.

---

Interview prep and DSA series, Part 3 (more algorithms): 4 of 5. Previous: Tries (prefix trees): autocomplete and prefix search.