LeetCode 252: Meeting Rooms

Problem Restatement

We are given a list of meeting time intervals.

Each interval contains:

[start, end]

A person can attend all meetings only if none of the meetings overlap.

We need to return:

• True if all meetings can be attended
• False if at least two meetings overlap

Two meetings overlap when one meeting starts before another meeting finishes.

Input and Output

Example function shape:

def canAttendMeetings(intervals: list[list[int]]) -> bool:
    ...

Examples

Example 1:

intervals = [[0, 30], [5, 10], [15, 20]]

The first meeting runs from 0 to 30.

The second meeting starts at 5.

Since:

the meetings overlap.

So the answer is:

False

Example 2:

intervals = [[7, 10], [2, 4]]

After sorting:

[[2, 4], [7, 10]]

The second meeting starts after the first meeting ends.

So the answer is:

True

Example 3:

intervals = [[1, 5], [5, 8]]

These meetings do not overlap.

The first meeting ends exactly when the second meeting starts.

So the answer is:

True

First Thought: Compare Every Pair

The simplest approach is to compare every meeting against every other meeting.

For two intervals:

[a_start, a_end]
[b_start, b_end]

they overlap when:

So we could check all pairs.

class Solution:
    def canAttendMeetings(self, intervals: list[list[int]]) -> bool:
        n = len(intervals)

        for i in range(n):
            for j in range(i + 1, n):
                a_start, a_end = intervals[i]
                b_start, b_end = intervals[j]

                if a_start < b_end and b_start < a_end:
                    return False

        return True

This works, but it checks too many pairs.

Problem With Brute Force

If there are n meetings, the brute force solution compares many interval pairs.

The time complexity becomes:

We can do better using sorting.

Key Insight

If intervals are sorted by start time, then we only need to compare neighboring meetings.

Why?

Suppose the meetings are sorted:

[start1, end1]
[start2, end2]
[start3, end3]

If meeting 2 does not overlap with meeting 1, and meeting 3 starts after meeting 2, then meeting 3 also cannot overlap with meeting 1.

So after sorting, checking adjacent intervals is enough.

The overlap condition becomes:

If this condition is true, the meetings overlap.

Algorithm

First, sort the intervals by start time.

intervals.sort()

Then scan from left to right.

For every meeting:

1. Compare its start time with the previous meeting’s end time.
2. If the current meeting starts before the previous one ends, return False.
3. Otherwise continue.

If we finish the scan without finding overlap, return True.

Correctness

After sorting, meetings appear in chronological order of start time.

Suppose we are currently examining:

previous = [prev_start, prev_end]
current = [curr_start, curr_end]

If:

then the current meeting begins before the previous meeting finishes. Therefore the meetings overlap, and attending all meetings is impossible.

If instead:

curr_start >= prev_end

then the current meeting starts at or after the previous meeting ends, so these two meetings do not overlap.

Because the intervals are sorted, any earlier meeting ends no later than prev_end. Therefore checking only neighboring intervals is sufficient to detect every possible overlap.

If no neighboring pair overlaps, then no meetings overlap at all, so attending all meetings is possible.

Complexity

The scan after sorting is linear.

Implementation

class Solution:
    def canAttendMeetings(self, intervals: list[list[int]]) -> bool:
        intervals.sort()

        for i in range(1, len(intervals)):
            prev_end = intervals[i - 1][1]
            curr_start = intervals[i][0]

            if curr_start < prev_end:
                return False

        return True

Code Explanation

We first sort the intervals:

intervals.sort()

Python sorts lists lexicographically, so intervals are sorted by start time automatically.

Then we scan neighboring intervals:

for i in range(1, len(intervals)):

For each pair:

prev_end = intervals[i - 1][1]
curr_start = intervals[i][0]

we check whether the current meeting starts too early.

if curr_start < prev_end:
    return False

If overlap exists, attending all meetings is impossible.

If the loop finishes, every interval is compatible with the next one.

So we return:

True

Testing

def run_tests():
    s = Solution()

    assert s.canAttendMeetings([[0, 30], [5, 10], [15, 20]]) is False
    assert s.canAttendMeetings([[7, 10], [2, 4]]) is True
    assert s.canAttendMeetings([[1, 5], [5, 8]]) is True
    assert s.canAttendMeetings([]) is True
    assert s.canAttendMeetings([[1, 2]]) is True
    assert s.canAttendMeetings([[1, 4], [2, 3]]) is False
    assert s.canAttendMeetings([[1, 3], [3, 5], [5, 7]]) is True

    print("all tests passed")

run_tests()

Test meaning: