Meeting Rooms

Problem

You are given a list of meetings, each described as a pair [start, end) — the meeting occupies the half-open time range from start up to (but not including) end. One person wants to attend every meeting on the list. Decide whether that is possible: return True if no two meetings overlap in time, and False otherwise.

Two meetings that merely touch — one ends at exactly the moment the next begins — do not conflict.

Examples

• intervals = [[0,30],[5,10],[15,20]] → False — the meeting [0,30] is still running when both [5,10] and [15,20] start.
• intervals = [[7,10],[2,4]] → True — [2,4] finishes before [7,10] begins.
• intervals = [[1,5],[5,8]] → True — the first ends exactly when the second starts; back-to-back is fine.

Constraints

• 0 <= len(intervals) <= 10^4
• 0 <= start < end <= 10^6

With up to 10^4 meetings, an O(n^2) pairwise check is borderline; O(n log n) is the expected bar.

Think about it first

TL;DR

Sort by start time, then check each adjacent pair — O(n log n) time, O(1) extra space (beyond the sort).

Approach 1 — Brute force

Check every pair of meetings for overlap. Two half-open intervals [a, b) and [c, d) overlap exactly when each one starts before the other ends: a < d and c < b.

from typing import List

def canAttendMeetings(intervals: List[List[int]]) -> bool:
    n = len(intervals)
    for i in range(n):
        for j in range(i + 1, n):
            a, b = intervals[i]
            c, d = intervals[j]
            if a < d and c < b:
                return False
    return True

Complexity: O(n^2) time, O(1) space.

With n = 10^4 that is ~5×10^7 pair checks. It may pass, but it does quadratic work for a problem that only needs the intervals sorted once.

Approach 2 — Sort + adjacent scan

The insight: once meetings are sorted by start time, any overlap must show up between neighbors. If meeting i overlaps some later meeting j, then it certainly overlaps meeting i+1, because i+1 starts no later than j does. So after sorting, one pass over adjacent pairs finds every conflict.

from typing import List

def canAttendMeetings(intervals: List[List[int]]) -> bool:
    intervals.sort(key=lambda it: it[0])
    for i in range(1, len(intervals)):
        prev_end = intervals[i - 1][1]
        cur_start = intervals[i][0]
        if cur_start < prev_end:
            return False
    return True

Walkthrough on [[0,30],[5,10],[15,20]]:

1. Sort by start → [[0,30],[5,10],[15,20]] (already sorted).
2. i = 1: previous ends at 30, current starts at 5. 5 < 30 → conflict → return False.

And on [[1,5],[5,8]]: i = 1 compares start 5 against previous end 5; 5 < 5 is false, so the loop finishes and we return True — touching endpoints are correctly allowed.

Complexity: O(n log n) time for the sort, O(1) extra space (Python’s sort uses O(n) internally, O(log n) typical accounting; the scan itself is O(1)).

Common pitfalls

• Using <= instead of < in the conflict test — that wrongly rejects back-to-back meetings like [1,5] and [5,8].
• Comparing only intervals[i] against intervals[0] after sorting, instead of against its immediate predecessor.
• Forgetting to sort at all and scanning adjacent pairs of the input order — the check is only valid on sorted data.
• Writing the pairwise overlap test as a <= d and c <= b (closed intervals) when the problem treats end times as exclusive.

Pattern takeaway

Sorting intervals by start time collapses a global “does anything overlap anything?” question into a local “does each interval overlap its neighbor?” question. Almost every intervals problem starts with this sort; what varies is what you track while sweeping — here just the previous end time.