4.27.4 — Meeting Rooms

LeetCode 252 · Easy

The problem

Given meeting times, return true if a person could attend all of them — that is, if no two meetings overlap.

[[0,30],[5,10],[15,20]]   →  false
[[7,10],[2,4]]            →  true

The pattern

Checking every pair is O(n^2). Sorting makes it O(n \log n) and reduces the check to one comparison per neighbour.

Sort by start. Then two meetings overlap if and only if some meeting begins before the previous one ends.

Why neighbours are enough: after sorting, if meeting i does not overlap meeting i+1, it cannot overlap anything after that either, because everything later starts even later. So a single pass over adjacent pairs catches every conflict.

The solution

Python

class Solution:
    def canAttendMeetings(self, intervals: List[List[int]]) -> bool:
        intervals.sort(key=lambda x: x[0])

        for i in range(1, len(intervals)):
            if intervals[i][0] < intervals[i - 1][1]:     # starts before the last ends
                return False

        return True

TypeScript

function canAttendMeetings(intervals: number[][]): boolean {
  intervals.sort((a, b) => a[0] - b[0]);

  for (let i = 1; i < intervals.length; i++) {
    if (intervals[i][0] < intervals[i - 1][1]) return false;
  }

  return true;
}

< and not <=. A meeting ending at 10 and another starting at 10 do not conflict — you walk out of one and into the next. This is the same convention as 4.27.3 and the opposite of 4.27.2.

Ask which convention applies. Every interval problem has this ambiguity, and the problem statement often does not say.

Complexity

O(n \log n) time from the sort, O(1) extra space.

An empty list or a single meeting returns true, with no special case — the loop simply does not run.

Where this goes next

• Meeting Rooms II — how many rooms are needed when meetings do overlap. Much more interesting, and it is 4.27.5.
• Meeting Rooms III — assign meetings to rooms and count which room is busiest, which needs two heaps.
• My Calendar I (LeetCode 729) — the streaming version: bookings arrive one at a time and each must be checked against everything booked so far. Sorting from scratch each time is O(n \log n) per booking; an ordered map or a balanced tree makes each check O(\log n). That is the natural follow-up when the input is a stream rather than a list.

What the interviewer will push on

"Why is checking neighbours enough?" After sorting by start, a non-conflict with the next meeting implies a non-conflict with every later one.

"Does a meeting ending exactly when another starts count as a conflict?" No here — ask on every interval problem, because the convention flips between them.

"Can you do better than O(n \log n)?" Not in general — detecting any overlap is at least as hard as sorting. If the times were small bounded integers you could bucket them, which is the 4.4.5 idea again.

"What if bookings arrive one at a time?" An ordered map for O(\log n) per check.

One thing to volunteer: state the sorted-neighbour argument. It is one sentence, and it is the reason the solution is a single pass rather than a nested loop.

Next: 4.27.5 Meeting Rooms II — counting how many overlap at once, and the sweep line that generalises far beyond meetings.