Greedy Algorithms6 min read

Interval Scheduling

Book as many non-overlapping meetings as possible — always pick the one that ends earliest
time:Fast · \(O(n \log n)\)space:Minimal · \(O(1)\)key insight:Sort by finish time, not start time

You're the office manager and you have one conference room. Employees keep submitting meeting requests, each with a start and end time. You want to fit in as many meetings as possible — they just can't overlap.

Which meetings do you pick? Here's the counterintuitive insight: always pick the meeting that ends earliest. Not the shortest. Not the earliest to start. The one that finishes first.

The Greedy Algorithm

1. Sort all meetings by finish time (ascending).
2. Pick the first meeting. Mark its finish time as your current "last used" time.
3. Scan the rest: if a meeting starts at or after the last finish time, take it and update last finish.
4. Skip any meeting that starts before the current last finish (it would overlap).

That's it. One sort + one linear scan = \(O(n \log n)\) total.

Why Not Sort by Start Time or Duration?

Sort by start time: A meeting that starts at 9am but runs until 6pm blocks everything. Early start ≠ leaving time for others.

Sort by duration: A 30-minute meeting might overlap with ten others. A 1-hour meeting might conflict with none. Short doesn't mean compatible.

Sort by finish time: This is the right criterion. Choosing the meeting that ends soonest leaves the maximum remaining window for future meetings. The exchange argument makes this rigorous.

Proof by Exchange Argument

Suppose an optimal schedule OPT doesn't start with the earliest-finishing meeting G. Let A be OPT's first pick. Since G finishes no later than A, we can swap A → G in OPT. G doesn't conflict with any later meeting that A didn't conflict with (it finishes at least as early). The schedule size doesn't decrease. Repeat until OPT matches greedy. So greedy is optimal.

Interval Partitioning (Bonus Variant)

What if you want to schedule all meetings but minimize the number of rooms used? Greedy again: sort by start time, assign each meeting to any available room. If none are free, open a new room. The minimum rooms needed equals the maximum depth — the largest number of overlapping meetings at any instant. A sweep-line with a min-heap computes this in \(O(n \log n)\).

Weighted Interval Scheduling (When Greedy Fails)

Add profits to meetings and maximize total profit instead of count. Now greedy fails — a highly profitable 8-hour meeting might be worth more than four 1-hour meetings. This variant needs Dynamic Programming: sort by finish time, define dp[j] = best profit using meetings 1..j, use binary search to find the last non-conflicting meeting.

Greedy interval scheduling: sort by finish time, greedily select non-overlapping intervals
Note: Earliest finish time is the magic sort key. Think of it this way: you want meetings that get out of the way quickly, freeing the room for everyone else. Ending early is more valuable than starting early.

Interval Scheduling — Maximum Non-Overlapping Meetings

def max_meetings(intervals):
    # Sort by finish time
    intervals.sort(key=lambda x: x[1])
    count = 0
    last_end = -1
    selected = []
    for start, end in intervals:
        if start >= last_end:
            selected.append((start, end))
            last_end = end
            count += 1
    return count, selected


meetings = [(1,4),(3,5),(0,6),(5,7),(3,9),(5,9),(6,10),(8,11),(8,12),(2,14),(12,16)]
n, chosen = max_meetings(meetings)
print(f"Max meetings: {n}")
for s, e in chosen:
    print(f"  [{s}, {e})")
Output
Max meetings: 4
  [1, 4)
  [5, 7)
  [8, 11)
  [12, 16)

Complexity

🗂️ Sort by finish timeThe dominant step — everything else is linear
One-time sort\(O(n \log n)\)
➡️ Greedy scanCheck each meeting once; take it or skip it
Single pass\(O(n)\)
📦 SpaceOnly track the finish time of the last selected meeting
Constant extra\(O(1)\)
🏢 Interval partitioning (min rooms)Priority queue tracks when each room next becomes free
Sort + min-heap\(O(n \log n)\)
💰 Weighted variant (max profit)Greedy fails here; DP with predecessor lookup is needed
DP + binary search\(O(n \log n)\)

Quick check

You have meetings: [1,10], [2,3], [4,5], [6,7]. Which ones does greedy (sort by finish time) select?

Continue reading

Greedy Pattern
Always grab the biggest slice of pizza — sometimes that's optimal, sometimes it isn't
→
Task Scheduling
Do homework by closest deadline first — miss nothing, earn the most
→
DP on Intervals
Solve tiny sections first, then merge them into bigger ones
→