Greedy Algorithms: The Matrix's Red Pill Choice

The Quest Begins (The "Why")

I remember the first time I tried to schedule a handful of back‑to‑to‑back interviews for a friend. I had a list of start and end times, and my gut told me to just pick the earliest‑starting meeting, then the next one that didn’t clash, and so on. After a few attempts I ended up with a schedule that felt… off. Some slots were left empty while others overlapped like a tangled mess of headphones. I spent an hour staring at the calendar, wondering if there was a simpler rule that could guarantee the maximum number of meetings without overlap.

That frustration is exactly what drives many interview questions: given a set of intervals, how do you pick the largest subset that don’t intersect? The brute‑force answer—trying every combination—explodes exponentially, and even a DP solution feels heavy for something that should feel intuitive. I needed a light‑bulb moment, a “red pill” that would make the pattern obvious.

The Revelation (The Insight)

The breakthrough came when I stopped looking at start times and started focusing on end times. Here’s the intuition:

If you always pick the interval that finishes earliest, you leave the most room left for the rest of the intervals.

Why does that work? Let’s prove it with an exchange argument, the kind of reasoning that feels like a magic trick once you see it.

Assume we have an optimal solution OPT that does not contain the earliest‑finishing interval I (the one with the smallest end). Since OPT is optimal, it must contain some other interval J that starts after I ends (otherwise we could just add I and improve the solution). Now replace J with I. Because I ends no later than J, the replacement cannot introduce any new conflict, and the number of intervals stays the same. We’ve transformed an optimal solution into another optimal solution that does contain I, without losing optimality.

By repeatedly applying this exchange, we can build an optimal solution that greedily picks the earliest‑finishing interval, then repeats the same logic on the remaining intervals that start after it ends. The greedy choice is safe, and the rest of the problem is identical in structure to the original.

That’s the whole secret: sort by end point, then walk forward, picking each interval whose start is after the last picked end. The proof guarantees we never miss a better solution.

Wielding the Power (Code & Examples)

Let’s turn that insight into code. I’ll use Python because it reads like pseudocode, but the same logic translates to any language.

The “before” – a naïve attempt

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

If you run this on [(1,4), (2,3), (3,5)] you’ll get 2 (picking (1,4) then (3,5)), but the optimal answer is 2 as well—seems fine. Try [(1,10), (2,3), (4,5), (6,7)]: the start‑time greedy picks (1,10) only → 1, while the true optimum is three intervals (2,3),(4,5),(6,7). The flaw is clear: picking by start can trap you in a long interval that blocks many short ones.

The “after” – the correct greedy

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

Why it’s O(n):

• Sorting dominates: O(n log n).
• The single scan after sorting is O(n). So overall O(n log n), but the core greedy step is linear—a detail interviewers love to hear you articulate.

Common traps (the “boss fights” on our quest)

1. Forgetting to sort – you’ll get a wrong answer on unsorted data.
2. Sorting by start instead of end – the classic pitfall we just saw.
3. Off‑by‑one on the compatibility check – using s > last_end excludes intervals that can start exactly when the previous one ends (e.g., (1,2) and (2,3) are fine). Use >=.
4. Mutating the list while iterating – avoid removing items; just keep a pointer to the last chosen end.

Real‑world interview flavors

Problem 1 – LeetCode 435: Non‑overlapping Intervals

Goal: Return the minimum number of intervals to remove so the rest are non‑overlapping.

Solution: The answer is total - max_non_overlapping(intervals). Compute the maximal compatible set with the greedy routine above, subtract from the length.

Problem 2 – LeetCode 452: Minimum Number of Arrows to Burst Balloons

Goal: Each balloon is a horizontal interval [x_start, x_end]. One arrow shot at x bursts all balloons whose interval contains x. Find the least arrows needed.

Solution: Again, sort by end. Fire an arrow at the end of the first balloon, then skip all balloons that start ≤ that arrow position. Repeat. The same “pick earliest end, then skip overlapping” pattern yields the optimal number of arrows.

Both problems reduce to the same core idea: choose the earliest finishing point, then discard everything that conflicts.

Why This New Power Matters

Once you internalize the “earliest finish” rule, a whole class of scheduling and resource‑allocation puzzles clicks into place. You can:

• Build a calendar optimizer that selects the max number of meetings.
• Design a CPU scheduler that maximizes throughput of non‑preemptive jobs.
• Solve variant problems like “minimum platforms needed at a railway station” by flipping the perspective (count overlaps instead of selecting).

The technique is lightweight, easy to explain in an interview, and—most importantly—feels right when you see it. It’s the kind of insight that turns a seemingly tangled problem into a clean, linear scan after a sort.

Your Turn

Here’s a mini‑quest for you: take the greedy routine above and adapt it to solve LeetCode 253: Meeting Rooms II (the minimum number of conference rooms required). Hint: think about how many intervals are “active” at any point instead of how many you can pick.

Give it a try, share your solution in the comments, and let’s keep the adventure going! 🚀