The Quest Begins (The "Why")
I still remember the first time I tried to schedule a bunch of back‑to‑back video calls for my team. I had a list of start and end times, and my naïve approach was to pick the meeting that started earliest, then the next one that didn’t clash, and so on. It felt logical, but after a few runs I kept ending up with gaps where I could have squeezed in an extra call. Frustrated, I dove into the problem and realized I was solving the classic activity selection puzzle without even knowing its name. The dragon I was slaying? Wasted time. And the weapon I needed wasn’t brute force—it was a simple, greedy idea that felt almost too obvious to be true.
The Revelation (The Insight)
The “aha!” moment came when I stopped thinking about when a meeting starts and started thinking about when it finishes. Imagine you have a bunch of intervals on a timeline. If you always pick the interval that finishes the earliest, you leave the maximum possible room for everything that comes after. Why does that work? Let’s prove it with an exchange argument, the kind of trick that feels like a Jedi mind trick but is actually pure logic.
Assume there’s an optimal schedule OPT that doesn’t start with the earliest‑finishing interval I. Replace the first interval in OPT with I. Since I ends no later than the interval it replaces, the rest of OPT can still fit unchanged—no overlaps are introduced, and we haven’t reduced the number of intervals. We can repeat this swap until the greedy choice appears at the front, proving that an optimal solution exists that begins with the greedy pick. By induction, the whole greedy chain is optimal. In plain English: picking the earliest finish never hurts you, and it often helps you squeeze in more later.
That insight turned my scheduling nightmare into a one‑liner: sort by end time, walk through the list, and take whatever starts after the last chosen end.
Wielding the Power (Code & Examples)
Let’s see the before and after. First, the brute‑force struggle (exponential, just for illustration):
def max_meetings_brute(intervals):
# intervals = [(start, end), ...]
from functools import lru_cache
intervals.sort() # by start, just to have a deterministic order
n = len(intervals)
@lru_cache(None)
def dfs(i, last_end):
if i == n:
return 0
# skip current
best = dfs(i + 1, last_end)
# take current if it fits
s, e = intervals[i]
if s >= last_end:
best = max(best, 1 + dfs(i + 1, e))
return best
return dfs(0, -float('inf'))
It works, but for 20 intervals you’re already looking at over a million recursive calls. Not interview‑friendly.
Now the greedy victory:
def max_meetings_greedy(intervals):
# intervals = [(start, end), ...]
# 1️⃣ Sort by finishing time (the greedy key)
intervals.sort(key=lambda x: x[1]) # O(n log n)
count = 0
last_end = -float('inf')
for s, e in intervals: # ❶ O(n) scan
if s >= last_end: # can we attend this?
count += 1
last_end = e # lock in the finish time
return count
Why it’s O(n) after the sort: the loop does constant work per interval, so the linear scan is O(n). The dominant term is the sort, O(n log n), which is unavoidable if the input isn’t already ordered.
Common traps (the “traps” on the quest)
- Sorting by start time – feels natural but fails badly (think of a long meeting that starts early but blocks many short ones).
-
Forgetting to update
last_end– you’ll count overlapping intervals as if they were sequential. -
Using
<instead of>=– you’ll miss intervals that start exactly when the previous one ends, which are allowed.
Let’s test it on two interview‑style problems.
Problem 1 – LeetCode 435: Non‑overlapping Intervals
Given intervals, remove the minimum number to make the rest non‑overlapping.
Answer: total intervals – max_meetings_greedy(intervals).
Because keeping the maximum number of non‑overlapping intervals is equivalent to removing the fewest.
Problem 2 – LeetCode 253: Meeting Rooms II (minimum rooms needed)
A twist: we need the maximum overlap, not the maximum count. The greedy idea still helps—sort start and end times separately, then walk through them, incrementing a counter when a meeting starts and decrementing when one ends. The peak of that counter is the answer. It’s the same “sweep line” spirit, just flipped.
Why This New Power Matters
Mastering this greedy pattern does more than solve interview puzzles—it trains you to spot problems where a locally optimal choice yields a global optimum. Suddenly, you see activity selection in resource allocation, CPU scheduling, even in selecting the best set of non‑conflicting features for a product roadmap. You stop grinding through exponential back‑tracking and start thinking in terms of “what leaves the most room for the future?” That shift in mindset is a superpower that pays off in real‑world systems design, not just LeetCode.
I remember the first time I applied this at work: we had to schedule data pipeline jobs with varying durations and deadlines. By sorting jobs by their finish‑time‑equivalent (the latest they could start without missing the deadline) and greedily picking, we cut the pipeline latency by 30 %. The team cheered, and I felt like I’d just used the Force to nudge the galaxy toward a better schedule.
Your Turn
Here’s a challenge: take a list of lecture halls with start and end times for various talks. Write a function that returns the maximum number of talks you can attend without moving between halls (you can only stay in one hall). Think about how the greedy idea changes when you have multiple identical resources. Drop your solution in the comments—or better yet, explain why the simple earliest‑finish greedy still works per hall, and where you’d need a tweak.
May your intervals always be short and your schedules ever‑greedy! 🚀
