Meeting Rooms

1. Problem & Core Objective

Given an array of meeting time intervals, determine whether a person could attend all of them.

[[0,30],[5,10],[15,20]]  →  false     ([0,30] clashes with both others)
[[7,10],[2,4]]           →  true
[[1,5],[5,9]]            →  true      (half-open: ends at 5, next starts at 5)

Constraints: 0 <= intervals.length <= 10^4, start_i < end_i, values up to 10^6.

What's actually being tested: that you turn an O(n²) all-pairs question into an O(n log n) neighbours-only one, and that you can say why checking neighbours is sufficient. Also, unavoidably, the closed-versus-half-open convention — meetings are the canonical half-open case, and getting it backwards inverts the answer on every touching pair.

2. First-Principles Thought Process

The literal question is quadratic

"Do any two intervals overlap?" is a statement about C(n,2) pairs. Checking them directly is O(n²) — fine at n = 10^4 in a pinch, but it ignores structure.

Sorting reduces pairs to neighbours

Sort by start. Now the claim is:

If any two intervals overlap, then some two adjacent intervals overlap.

Proof: suppose a[i] and a[k] overlap with i < k. Sorted by start, a[i][0] <= a[j][0] <= a[k][0] for every j between them. Overlap means a[k][0] < a[i][1]. So a[j][0] <= a[k][0] < a[i][1], which means a[j] overlaps a[i] too — and by induction the adjacent pair a[i] and a[i+1] overlaps.

So n−1 comparisons replace C(n,2), and the only cost is the sort.

This is the same "sorting makes one backward comparison sufficient" invariant as Merge Intervals, used to answer a yes/no question instead of building a result.

The convention matters more here than anywhere

A meeting from 1 to 5 and one from 5 to 9 do not clash — you leave one room and walk into the next. That's the half-open convention [start, end), and it makes the test:

if (a[i][0] < a[i-1][1]) return false;      // strict <

Using <= would report a conflict on every back-to-back pair, which for a realistic calendar is most of them. This is the single decision that determines whether the function is right or wrong, and it cannot be inferred from the code — only from asking.

LeetCode 252 uses half-open. Merge Intervals uses closed. Both are defensible for their domains; neither is "the" convention.

This problem is a stepping stone

Meeting Rooms asks whether the peak concurrency exceeds 1. Meeting Rooms II asks what the peak concurrency actually is. Framing it that way makes the follow-up immediate rather than a new problem — and it's the framing to volunteer.

3. Solution Paths

Approach 1 — Brute force, all pairs

public boolean canAttendMeetings(int[][] intervals) {
    for (int i = 0; i < intervals.length; i++)
        for (int j = i + 1; j < intervals.length; j++)
            if (intervals[i][0] < intervals[j][1] && intervals[j][0] < intervals[i][1])
                return false;
    return true;
}

• Time O(n²) · Space O(1)

The reference the sorted version was checked against, on 4,000 random inputs.

Counter-questions on this approach

⭐ "Explain the overlap test."

Two half-open intervals overlap iff each starts strictly before the other ends. Equivalently max(starts) < min(ends).

It's symmetric, which is required because the pair is unordered — I don't know which comes first. The one-sided test the sorted version uses is valid only because sorting establishes which is which.

"Is O(n²) actually too slow here?"

At n = 10^4 it's 5 × 10^7 comparisons — roughly a tenth of a second in Java, so it would pass. I'd say that honestly rather than pretending it's infeasible.

The reason to sort isn't this problem's limits; it's that the sorted form extends to Meeting Rooms II and the all-pairs form doesn't.

"Does it short-circuit usefully?"

On a conflicting input, yes — often immediately. On a conflict-free input it must check every pair, so the worst case is the true case. That's the opposite of the usual intuition and worth noting.

Approach 2 — Sort by start, check neighbours (optimal)

public boolean canAttendMeetings(int[][] intervals) {
    Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
    for (int i = 1; i < intervals.length; i++)
        if (intervals[i][0] < intervals[i - 1][1]) return false;   // starts before the previous ends
    return true;
}

• Time O(n log n) · Space O(log n) for the sort

Counter-questions on this approach

⭐ "Why is checking adjacent pairs enough?"

Because sorting by start makes overlap propagate backwards. If a[i] and a[k] overlap with i < k, then a[k][0] < a[i][1]. Any a[j] in between has a[j][0] <= a[k][0] < a[i][1], so a[j] overlaps a[i] as well. Applying that repeatedly, the adjacent pair a[i], a[i+1] must overlap.

Contrapositive: if no adjacent pair overlaps, no pair does. So n−1 checks decide a property of C(n,2) pairs.

⭐ "Why < and not <=?"

Because meetings are half-open. A meeting ending at 5 and one starting at 5 don't conflict — you walk from one room to the other.

With <=, [[1,5],[5,9]] would return false, and on a realistic calendar most adjacent pairs are back-to-back, so it would report conflicts almost everywhere. This is the decision I'd confirm with the interviewer before writing the line.

"Does comparing against only a[i-1] miss a longer earlier meeting?"

No, and this is the subtle part. Suppose a[i-2] is very long and extends past a[i]'s start, while a[i-1] is short and doesn't. Then a[i-1][0] >= a[i-2][0] and a[i-1][0] < a[i-2][1] — so a[i-2] and a[i-1] already overlap, and we returned false one iteration earlier.

In other words, we never reach i with an unreported long meeting still open. The early return is what makes the local check globally sound.

"What about ties in the sort?"

Two meetings with the same start always conflict (both have positive length), and the check catches it whichever order they land in: a[i][0] == a[i-1][0] < a[i-1][1]. So no tie-break is needed — worth verifying rather than assuming.

"Empty or single-element input?"

Both return true with no special case: the loop from i = 1 doesn't run. 0 <= intervals.length is in the constraints, so this is worth pointing at.

"Does Arrays.sort mutate the caller's array?"

Yes, in place. If the caller's ordering matters, intervals.clone() first — a shallow clone of the outer array is enough, since the rows are only read.

Approach 3 — Separate and sweep the endpoints

public boolean canAttendMeetings(int[][] intervals) {
    int n = intervals.length;
    int[] starts = new int[n], ends = new int[n];
    for (int i = 0; i < n; i++) { starts[i] = intervals[i][0]; ends[i] = intervals[i][1]; }
    Arrays.sort(starts);
    Arrays.sort(ends);
    for (int i = 1; i < n; i++)
        if (starts[i] < ends[i - 1]) return false;      // the i-th meeting begins before the i-th ends
    return true;
}

• Time O(n log n) · Space O(n)

Counter-questions on this approach

⭐ "You've destroyed the pairing between starts and ends. Why is that valid?"

Because the question only concerns counts over time, not which start belongs to which end. If the i-th smallest start comes before the i-th smallest end, then at that moment i+1 meetings have begun and only i have finished — so two are running at once.

That decoupling is the key idea of the whole sweep-line family, and it's what Meeting Rooms II generalises to count rooms.

"Is this better than Approach 2?"

Not for this problem — same complexity, more space, and two sorts of int[] instead of one of int[][]. In practice the primitive sorts are faster because there's no comparator call and no boxing, so the constant is better.

Its real value is that it's the same shape as Meeting Rooms II. Writing it here means the follow-up is a two-line change.

"Why Arrays.sort(int[]) rather than a comparator?"

Primitive arrays have no comparator overload — they use dual-pivot quicksort, which is unstable and has an adversarial O(n²) case that doesn't arise with non-adversarial data. Object arrays use TimSort and accept a comparator (04).

4. Why the Optimal Solution Wins

O(n log n) is optimal in the comparison model — detecting any overlap solves element distinctness, which has an Ω(n log n) lower bound.

Write Approach 2, and mention Approach 3 as the bridge to the follow-up. The interviewer asking Meeting Rooms is almost always going to ask Meeting Rooms II next.

5. Java Prerequisites

Sorting int[][] by a column

Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));

Extracting columns into primitive arrays

int[] starts = new int[n], ends = new int[n];
for (int i = 0; i < n; i++) { starts[i] = intervals[i][0]; ends[i] = intervals[i][1]; }
// or: int[] starts = Arrays.stream(intervals).mapToInt(a -> a[0]).toArray();

The stream version is one line and allocates an intermediate; the loop is faster and equally clear.

Loops that start at 1

for (int i = 1; i < n; i++) if (a[i][0] < a[i-1][1]) return false;

Naturally handles n = 0 and n = 1 — no guard needed, which is the reason to prefer it over indexing i+1 from 0.

Shallow clone to protect the caller

int[][] a = intervals.clone();       // new outer array, same rows — enough if rows aren't mutated

6. Interview Communication Guide

Clarifying questions: Do back-to-back meetings conflict — does one ending at 5 clash with one starting at 5 (no, meetings are half-open; this is the decision that flips the answer)? Can the list be empty (yes — trivially true)? Can two meetings have identical times (yes, and they conflict)? May I sort the input in place (it reorders the caller's array — I'll clone if that matters)?

The pitch

"Literally this asks whether any two of the n intervals overlap, which is C(n,2) pairs. Sorting by start collapses that to n−1 adjacent comparisons.

Here's why adjacency is enough. Suppose two intervals i and k overlap with i before k in sorted order. Then k starts before i ends. Every interval j between them starts at or after i and at or before k — so j also starts before i ends, meaning j overlaps i too. Push that down and the adjacent pair i, i+1 must overlap. Contrapositive: no adjacent overlap means no overlap anywhere.

There's a subtlety worth stating: comparing only against the immediately previous meeting can't miss a long earlier one, because if an earlier meeting were still running it would already have conflicted with the meeting in between, and we'd have returned false then.

The test is intervals[i][0] < intervals[i-1][1], strictly less than, because meetings are half-open — a meeting ending at 5 and one starting at 5 are fine. Using <= would report a conflict on every back-to-back pair, which on a real calendar is most of them. I'd confirm that convention before writing the line.

O(n log n) from the sort, O(1) extra.

If the follow-up is 'how many rooms do you need', I'd separate the starts and ends into two sorted arrays and sweep them with two pointers — the same shape, counting concurrency instead of testing it against 1."

Edge cases to volunteer:

Ask about [[1,5],[5,9]] before writing the comparison. It costs one sentence and it is the only input whose expected answer you cannot derive from the problem statement alone.

7. Follow-Up Questions — Modified Constraints

⭐ "How many rooms would you need?"

Meeting Rooms II — the peak number of simultaneous meetings. Sort starts and ends separately and sweep with two pointers, or keep a min-heap of end times. O(n log n).

Framing it as "this problem asks whether the peak exceeds 1; that one asks what the peak is" makes it the same problem rather than a new one.

⭐ "Return the conflicting pair, not just a boolean."

The sorted version already has it — intervals[i] and intervals[i-1] at the moment it returns false. Carry original indices through the sort if the caller needs positions rather than values.

Worth noting it finds a conflicting pair, not all of them, and not necessarily the earliest by original index.

"What if a person could attend meetings in k rooms at once?"

Compute the peak concurrency and compare it to k — Meeting Rooms II plus one comparison. The boolean version is the k = 1 case.

"What if meetings had travel time between rooms?"

Pad each meeting's end by the travel time, then run the same check. If travel time depends on the specific pair of rooms, it becomes a scheduling problem with pairwise constraints rather than a sweep — considerably harder.

"What if meetings recurred weekly?"

Reduce every meeting modulo the week and the problem becomes circular, since a meeting can wrap past midnight Sunday. Split any wrapping meeting into two, then run the linear check. The split is what keeps the total order intact.

"What if the input were a stream of 10^9 meetings?"

Sorting is out. If they arrive already sorted by start, the check is one pass in O(1) memory. Otherwise it's an external sort — or, if only a yes/no answer is needed and coordinates are bounded, a difference array over the time axis in O(range).

"How would you test this?"

Randomized differential testing against the O(n²) all-pairs version — which is what I did here, 4,000 random inputs, agreeing on every one. For a problem this small that's more convincing than hand-picked cases, and it's specifically what catches a < / <= mistake, since random inputs produce exact touches regularly.