Meeting Rooms

This is the warm-up of the interval family, and often the first half of a two-part question whose second half is Meeting Rooms II. It is short, but it teaches the one fact every interval solution depends on: after sorting, only neighbours matter.

The problem

You are given a list of meetings, each as [start, end]. Decide whether one person could attend all of them, which means no two meetings overlap. A meeting that ends at 5 and one that starts at 5 do not clash.

• [[9, 12], [1, 5], [5, 9]] → True. In time order: 1–5, 5–9, 9–12. Each one starts exactly when the last ends.
• [[1, 5], [8, 11], [4, 7]] → False. The meeting 4–7 starts before 1–5 ends.

Constraints: 0 ≤ n ≤ 10⁴, 0 ≤ start < end ≤ 10⁶.

Clarifying questions

• Does a meeting ending at 5 clash with one starting at 5? No — the person walks from one room to the next.
• Can the list be empty? Yes; then the answer is True.
• Are the meetings sorted? No.
• Do I need to return which meetings clash? No, only yes or no. (It is a follow-up.)

Approach 1: compare every pair

Two meetings clash when each starts before the other ends. With touching allowed, the comparison is strict.

1def can_attend_all_pairs(meetings: list[list[int]]) -> bool:2    """Compare every pair of meetings."""3    for i in range(len(meetings)):4        for j in range(i + 1, len(meetings)):5            a, b = meetings[i], meetings[j]6            if a[0] < b[1] and b[0] < a[1]:      # strict: touching is fine7                return False8    return True

Time O(n²), space O(1). At n = 10⁴ that is 5 × 10⁷ pair checks — several seconds in Python, and it only gets worse. It also throws away the structure: time is one-dimensional, and a person's day is a line, not a web of pairs.

A second simple idea is to mark time itself: keep a set of every minute that is booked, and report a clash when a meeting wants a minute that is already taken. It is easy to write, but its cost depends on the length of the meetings, not on how many there are. With times up to 10⁶, a single meeting can mark a million minutes, and 10⁴ long meetings would mark 10¹⁰. When the constraints give large time values, any solution that walks through time unit by unit is out.

The key insight

Sort the meetings by start. If any two meetings clash, then two neighbouring meetings clash.

Here is why. Suppose meeting a clashes with a later meeting c, and some meeting b sits between them in sorted order. Then b starts no later than c does, and c starts before a ends. So b also starts before a ends, and a and b — which are neighbours, or closer to being neighbours — clash too. Repeat the argument and you reach a neighbouring pair that clashes.

Put numbers on it. Sorted by start: a = [1, 10], b = [2, 3], c = [5, 6]. a clashes with c, which is not its neighbour. But b starts at 2, which is before a ends at 10, so a and b — neighbours — clash as well, and the scan stops there. It does not matter that it found a different pair; the question is only whether some clash exists.

So after sorting you never need a pair of loops. Walk once, and compare each meeting with the one just before it. That turns O(n²) into the cost of the sort.

Approach 2: sort, then check neighbours

1def can_attend_all(meetings: list[list[int]]) -> bool:2    """Sort by start; only neighbours in that order can clash."""3    ordered = sorted(meetings, key=lambda m: m[0])4    for previous, current in zip(ordered, ordered[1:]):5        if current[0] < previous[1]:             # starts before the last one ends6            return False7    return True

1. Sort by start, into a new list so the caller's list is not changed.
2. Pair each meeting with the next one using zip(ordered, ordered[1:]).
3. If a meeting starts strictly before the previous one ends, return False.
4. If the loop finishes, no neighbours clash, so nothing clashes: return True.

Dry run on [[1, 5], [8, 11], [4, 7]]. Sorted by start: [1, 5], [4, 7], [8, 11].

And on [[9, 12], [1, 5], [5, 9]], sorted to [1, 5], [5, 9], [9, 12]:

Complexity. The sort is O(n log n) and the scan is O(n), so O(n log n) time. Space O(n) for the sorted copy; sorting in place brings it to the sort's own overhead, at the price of changing the input.

Edge cases

• Empty list or one meeting: zip produces no pairs, and the answer is True.
• Touching meetings, [1, 5] then [5, 9]: 5 < 5 is false, so they do not clash. With <= instead, the answer flips to False — the whole convention lives on that one character.
• Identical meetings, [[2, 4], [2, 4]]: 2 < 4, so they clash.
• One long meeting covering others, [[1, 10], [2, 3]]: sorted, 2 < 10, clash. The neighbour check still catches it.

Follow-ups

• "Return the first pair that clashes." Return (previous, current) instead of False. The first clashing neighbours in sorted order are the earliest clash.
• "How many rooms would you need so that every meeting can happen?" That is Meeting Rooms II, later in this section: a min-heap of end times.
• "A person already has a sorted calendar; can a new meeting be added?" Binary search for where the new start would go, and check only the neighbour before and the neighbour after: O(log n).