Interval SchedulingInterval scheduling

01Why it exists

Reach for it when you see:Meeting rooms, time slots, non-overlapping, the most you can fit in, merging intervals, how many run at once, sorting by finish time.

02The core idea

Interval scheduling: given n intervals [s, e), pick as many as possible that do not overlap. The greedy strategy is to sort by finish time and sweep from the front, taking an interval whenever its start is no earlier than the finish time of the last one chosen, and updating that finish time as you go. The code is one sort and one variable, last_end: O(n log n) time and O(1) extra space.

Why finish time, rather than start time or length? An exchange argument. The first interval the greedy takes, G₁, is the earliest-finishing of them all, so the first interval to finish in any optimal solution, O₁, finishes no earlier than G₁ does. Swap O₁ for G₁: every other interval in that optimal solution starts after O₁ has finished, and therefore after G₁ has finished too, so the swapped solution still has no clashes. There is therefore an optimal solution that begins with G₁, and the same argument then applies to whatever remains among the intervals starting at or after G₁'s finish. Sorting by start time lets one long early meeting eat the entire day; sorting by length lets one short meeting that straddles two others rob you of both. Counterexamples are easy to construct for either.

The same set of intervals with a different question needs a different sort key. Merging overlapping intervals (LeetCode 56) sorts by start time: sweeping through, whenever a new interval's start is ≤ the current block's finish, extend that block by taking the max of the two finishes, and otherwise begin a new block. The fewest meeting rooms (LeetCode 253) asks how many meetings are in progress at the busiest instant: split each interval into a start event of +1 and an end event of −1, sort the events by time, sweep with a running sum, and the largest value it reaches is the answer. That technique is called a sweep line.

Think the boundary through: one meeting ends at 10:00 and another starts at 10:00 — is that a clash? Problems normally say it is not, which makes the test s >= last_end. In the sweep line, end events have to sort before start events at the same instant, or you will count one room too many. One more thing that catches people out is LeetCode 435, "remove the fewest intervals so that none overlap". It looks like a new problem, but the answer is just n minus the number that interval scheduling picks.

03The algorithm

1. 1Sort every interval by finish time, smallest first.
2. 2Initialise last_end = −∞, the finish time of the last interval chosen so far.
3. 3Take each interval (s, e) in turn: if s >= last_end, choose it and set last_end = e; otherwise skip it.
4. 4When the sweep ends you have the answer: the chosen intervals do not overlap, and no larger set exists.
5. 5Variations: to merge, sort by start time and extend the finish instead; to count how many run at once, switch to a sweep line with +1 at each start and −1 at each end.

04Interactive demo

Nine meetings are competing for one room. The first step sorts them by finish time, and after that each step considers one meeting: if its start is no earlier than the amber line (the running finish time), it goes in, otherwise it is skipped. Watch how long meetings like B "Interview" and G "One-on-one" get eliminated without any special handling.

05Code

Interval scheduling itself, plus its two most common variations: merging overlapping intervals, and counting the fewest rooms. All three are a sort followed by a single pass, and only the sort key and what happens during the pass change.

# Interval scheduling: the most meetings one room can host (greedy by finish time)
def max_meetings(intervals):
    intervals = sorted(intervals, key=lambda iv: iv[1])   # sort by finish time
    chosen = []
    last_end = float("-inf")
    for s, e in intervals:
        if s >= last_end:                    # no clash with the previous one (touching ends are fine)
            chosen.append((s, e))
            last_end = e
    return chosen


# Merge overlapping intervals (LeetCode 56): sort by start time, join whatever touches
def merge_intervals(intervals):
    intervals = sorted(intervals, key=lambda iv: iv[0])
    merged = []
    for s, e in intervals:
        if merged and s <= merged[-1][1]:    # overlaps the previous block
            merged[-1][1] = max(merged[-1][1], e)
        else:
            merged.append([s, e])
    return merged


# Fewest rooms needed (LeetCode 253): a sweep line for how many meetings run at once
def min_rooms(intervals):
    events = []
    for s, e in intervals:
        events.append((s, 1))                # a start: +1
        events.append((e, -1))               # an end: -1
    events.sort()                            # at the same instant ends come before starts (-1 < 1)
    rooms = best = 0
    for _, d in events:
        rooms += d
        best = max(best, rooms)
    return best


if __name__ == "__main__":
    mtgs = [(0, 3), (1, 6), (2, 4), (4, 7), (6, 8), (7, 11), (8, 12), (10, 14), (13, 16)]
    print(max_meetings(mtgs))                # [(0, 3), (4, 7), (7, 11), (13, 16)]
    print(merge_intervals([[1, 3], [2, 6], [8, 10], [9, 12]]))   # [[1, 6], [8, 12]]
    print(min_rooms([(0, 30), (5, 10), (15, 20)]))              # 2

06Practice

• LeetCode 2446Determine if Two Events Have Conflict (do two intervals overlap?)Easy
• LeetCode 435Non-overlapping Intervals (n minus the interval-scheduling answer)Medium
• LeetCode 56Merge IntervalsMedium
• LeetCode 2406Divide Intervals Into Minimum Number of Groups (the fewest rooms again: a sweep line or a min-heap)Medium
• LeetCode 452Minimum Number of Arrows to Burst BalloonsMedium
• LeetCode 1353Maximum Number of Events That Can Be Attended (each day, take the one that finishes earliest)Medium