Meeting Rooms

Meeting Rooms is a classic interval problem. It asks one simple question — can a single person attend every meeting? — and teaches the move at the heart of nearly all interval problems: sort first, then sweep.

The slow way first

The obvious idea: compare every pair of meetings and check if any two overlap. That works, but it is O(n²) — for each meeting you scan all the others.

The question to ask: if I could line the meetings up in a sensible order, would I still need to compare every pair? If they are sorted by start time, then any overlap must involve neighbors — a meeting can only collide with the one right before it. That drops the work to a single pass.

The idea: sort, then check neighbors

Sort the meetings by start time. Now walk through them in order. For each meeting, look at the one before it: if the current meeting starts before the previous one ends, the two overlap and the answer is False. If we reach the end without any overlap, the answer is True.

The key insight: sorting collapses a pairwise problem into a neighbor problem. Once the starts are in order, a non-overlap with the previous meeting guarantees non-overlap with all earlier ones too.

Walk through it

Step through the animation. The meetings are drawn as timeline bars, already sorted by start. The pointer i sweeps left to right, comparing each meeting's start against the previous meeting's end:

• i = 1: [5, 10] vs [0, 5] — is 5 < 5? No. The meetings only touch end-to-start, and a strict < lets that pass. Clear.
• i = 2: [10, 18] vs [5, 10] — is 10 < 10? No. Another touching pair. Clear.
• i = 3: [15, 25] vs [10, 18] — is 15 < 18? Yes. This meeting starts while [10, 18] is still running, so the bars collide — the overlap flashes and we return False on the spot.

Notice how the first two comparisons pass cleanly before the third one fails: the answer is decided only when a real overlap appears, not on the very first check.

Pseudocode

sort intervals by start time
for i from 1 to n - 1:
    if intervals[i].start < intervals[i - 1].end:
        return False              # this meeting overlaps the previous one
return True                       # no overlaps anywhere

The Python solution

def can_attend(intervals):
    intervals.sort(key=lambda iv: iv[0])
    for i in range(1, len(intervals)):
        if intervals[i][0] < intervals[i - 1][1]:
            # starts before the previous one ends
            return False
    return True

• intervals.sort(key=lambda iv: iv[0]) orders the meetings by start time — the step that makes neighbor-only checks valid.
• The loop starts at i = 1 so we always have a previous meeting at i - 1 to compare against.
• intervals[i][0] is the current start; intervals[i - 1][1] is the previous end.
• If the current start is strictly less than the previous end, they overlap and we return False immediately.
• Reaching the final return True means every neighbor pair was clear, so one person can attend them all.

Complexity

The sort costs O(n log n) and dominates the linear sweep that follows. We use only O(1) extra space (ignoring the sort). That trade — sort to expose structure, then make a single neighbor pass — is the backbone of almost every interval problem.

When this pattern shows up

Practice