The Matrix: Greedy Algorithms Unveiled

The Quest Begins (The "Why")

I still remember the first time I stared at a LeetCode problem that asked for the minimum number of intervals to remove so the rest don’t overlap. My brain went straight to “let’s try every subset” – a brute‑force force‑check that felt like trying to solve a Rubik’s cube blindfolded. After a few minutes of frantic recursion I realized the exponential blow‑up was going to melt my laptop. I needed a smarter way, something that felt less like hacking through a dungeon and more like walking through a doorway that just opens when you approach it the right way. That’s when I remembered the greedy paradigm: make the locally optimal choice and hope it leads to a global optimum. It sounded almost too simple, but the payoff was worth the risk.

The Revelation (The Insight)

The activity‑selection problem (a.k.a. interval scheduling) is the poster child for why greed works here. Imagine you have a bunch of meetings, each with a start and finish time. You want to attend as many as possible. The key insight is: if you always pick the meeting that finishes earliest, you leave the most room for the rest.

Why does that guarantee optimality? Let’s sketch the proof in plain English. Suppose an optimal solution O picks its first meeting f₁. Our greedy algorithm picks g₁, the meeting with the earliest finish time. By definition, g₁ finishes no later than f₁. Replace f₁ with g₁ in O – the new set is still feasible because g₁ ends earlier, and it’s just as large as O. Now we’ve reduced the problem to the remaining meetings that start after g₁ finishes, and we can repeat the argument. By induction, the greedy choice never hurts optimality.

In short: earliest finish → maximal remaining time → optimal count. It’s a neat exchange argument that feels like a magic trick once you see it.

Wielding the Power (Code & Examples)

The Struggle (Brute Force)

def min_removals_bruteforce(intervals):
    # try every subset – exponential!
    n = len(intervals)
    best = float('inf')
    from itertools import combinations
    for r in range(n + 1):
        for combo in combinations(intervals, r):
            # check if combo is non‑overlapping
            ok = True
            prev_end = -float('inf')
            for s, e in sorted(combo, key=lambda x: x[0]):
                if s < prev_end:
                    ok = False
                    break
                prev_end = e
            if ok:
                best = min(best, n - r)
    return best

This works for tiny inputs but explodes past n ≈ 20.

The Victory (Greedy)

def min_removals_greedy(intervals):
    # 1. sort by ending time
    intervals.sort(key=lambda x: x[1])
    # 2. greedy walk
    removals = 0
    prev_end = -float('inf')
    for start, end in intervals:
        if start < prev_end:          # overlap → we must drop this one
            removals += 1
        else:                         # take it
            prev_end = end
    return removals

What just happened? After sorting, we sweep once, keeping the end of the last chosen interval. If the next interval starts before that end, it overlaps and we count it as a removal; otherwise we keep it and move the marker forward.

Common traps

• Forgetting to sort by end time (sorting by start leads to sub‑optimal results).
• Counting the interval we keep instead of the one we drop – double‑check whether you’re incrementing on overlap or on acceptance.
• Assuming the input is already sorted; never trust that in an interview.

Two Interview‑Style Problems

1. LeetCode 435 – Non‑overlapping Intervals
   
   Input: [[1,2],[2,3],[3,4],[1,3]]
   
   Goal: Minimum removals so the rest don’t overlap.
   
   Solution: Apply the greedy routine above → answer 1 (remove [1,3]).

2. LeetCode 452 – Minimum Number of Arrows to Burst Balloons
   
   Idea: Each balloon is an interval [x_start, x_end]. An arrow shot at x bursts all balloons whose intervals contain x. The greedy trick is identical: sort by end, shoot whenever the current balloon starts after the last arrow position.
   
   Code is a one‑liner change: replace removals with arrows and increment when start > last_arrow.

Both problems run in O(n log n) for the sort plus O(n) for the linear scan – the greedy part is truly linear.

Why This New Power Matters

Mastering this pattern does more than solve a single LeetCode question. It gives you a lens to spot when a problem exhibits the “earliest finish” or “earliest deadline” property: scheduling, resource allocation, even certain network flow reductions. When you see it, you can replace a frightening exponential search with a clean, provably correct sweep.

In real‑world systems, think of allocating meeting rooms, scheduling CPU tasks, or even planning drone delivery windows – the same greedy core applies. Knowing the proof lets you explain why your solution works, which is gold in interviews where interviewers love to hear the reasoning behind the code.

So next time you face an interval‑style puzzle, remember: pick the earliest finisher, trust the exchange argument, and let the rest fall into place. It’s not just a trick; it’s a reliable super‑power that turns a nightmare into a smooth, linear‑time victory.

---

Your turn: Grab a calendar view of your next week, treat each event as an interval, and compute the maximum number of events you can attend without overlap using the greedy method. Share your result or a tricky case you stumbled upon – let’s keep the quest going!