Meeting Rooms

How it works

We want to determine whether a person can attend all meetings without any overlaps.

A key observation is:

• if meetings are sorted by their start time, then
• we only need to check adjacent meetings for overlap

Why this works:

• if two meetings overlap, they must appear next to each other after sorting by start time
• there is no need to compare every pair

So by sorting once and doing a single pass, we can efficiently detect any conflict.

Steps

1. Sort all meetings by their start time.
2. Iterate through the sorted list starting from the second meeting:
3. For each pair of adjacent meetings:
   • let i1 be the previous meeting
   • let i2 be the current meeting
4. If i1[1] > i2[0]:
   • the meetings overlap
   • return false
5. If the loop finishes without finding any overlap:
   • return true

Complexity

• Time complexity: O(n log n)
• Space complexity: O(1) or O(n) depending on the sorting algorithm.

Things to watch for

Using the Wrong Overlap Condition

Meetings overlap when prev[1] > curr[0], not prev[1] >= curr[0]. If one meeting ends exactly when another starts, they do not overlap and can both be attended.

Forgetting to Sort Before Comparing Adjacent Meetings

The sorting approach only works when meetings are sorted by start time. Comparing adjacent meetings in an unsorted list will miss overlaps between non-adjacent intervals.

from typing import List

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

        for i in range(1, len(intervals)):
            i1 = intervals[i - 1]
            i2 = intervals[i]

            if i1[1] > i2[0]:
                return False
        return True

class Solution {
public:
    bool canAttendMeetings(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), [](auto& x, auto& y) {
            return x[0] < y[0];
        });
        for (int i = 1; i < intervals.size(); ++i) {
            if (intervals[i][0] < intervals[i - 1][1]) {
                return false;
            }
        }
        return true;
    }
};