Meeting Rooms (LeetCode 252)

The problem

You get a list of meetings, each as [start, end]. Decide whether one person can attend all of them, which means no two meetings overlap. A meeting that ends at time 10 does not clash with one that starts at time 10.

Input:  [[0, 30], [5, 10], [15, 20]]
Output: False

The meeting [5, 10] starts while [0, 30] is still running.

How to think about it

Start with brute force. Compare every pair of meetings and check whether they overlap. That is O(n²) pairs. Correct, but it ignores the structure of time.

The key insight: after sorting by start, only neighbours can clash. Once meetings are in start order, if meeting i does not overlap meeting i-1, it cannot overlap anything earlier either, as long as no clash has been found so far: every earlier meeting ended no later than i-1 started. So one pass comparing each meeting’s start with the previous meeting’s end is enough. The first time a start is before the previous end, you have a clash.

Which pattern is this? Merge intervals. The tell is [start, end] pairs and the word “overlap”. As the lesson says, sorting by start is the whole trick.

Approach

1. Sort the meetings (Python sorts lists by first element, then second).
2. For each meeting from index 1 on, if its start is strictly less than the previous meeting’s end, return False.
3. If no clash is found, return True.

Solution

def can_attend_meetings(intervals):
    intervals.sort()                                  # by start time
    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
# can_attend_meetings([[0,30],[5,10],[15,20]]) -> False

Dry run

After sorting: [[0, 30], [5, 10], [15, 20]].

The loop stops at the first clash. (Had it continued, i = 2 compares 15 with 10, which is fine.)

Complexity

• Time: O(n log n). The sort dominates; the scan is O(n).
• Space: O(1) extra. The list is sorted in place (Python’s sort may use up to O(n) temporary memory internally).

Edge cases and pitfalls

• Empty list or a single meeting returns True; the loop body never runs.
• Back-to-back meetings such as [[1, 5], [5, 8]] return True. Use <, not <=, so touching ends are allowed.
• Skipping the sort breaks the neighbour check: unsorted [[10, 20], [0, 5]] compares 0 with 20 and wrongly reports a clash, although the meetings are hours apart.
• sort() mutates the input. If the caller needs the original order, sort a copy with sorted(intervals).

Related problems

• Meeting Rooms II (LeetCode 253): instead of yes/no, count how many rooms you need.
• Merge Intervals (LeetCode 56): the same sort-then-sweep, merging the overlaps you find.
• My Calendar I (LeetCode 729): the same overlap test, with bookings arriving one at a time.