252. Meeting Rooms

Meeting Rooms is the gentlest entry into the interval patterns family, and it earns that spot by teaching the one move the whole family shares: sort by start time first, and suddenly overlaps become a local check between neighbors instead of a comparison of every pair.

The problem

You’re given a list of meetings, each written as a [start, end] pair, and you have exactly one room. Return true if a single person could sit through all of them without a clash, false if any two collide in time. (Full statement on LeetCode.)

So [[0, 30], [5, 10]] is false — the second meeting starts while the first is still running. But [[7, 10], [2, 4]] is true; they never touch.

Intuition: after sorting, you only fight your neighbor

The naive read is “compare all pairs” — $O(n^2)$ — but almost none of those comparisons carry information. Sort the meetings by start time and the structure collapses: the only meeting you ever have to check against the current one is the one right before it. (A conflict can absolutely involve a non-adjacent pair — in [0,10], [2,3], [4,5] the last overlaps the first — but the scan catches it earlier, at the adjacent pair that also overlaps.)

Why is the neighbor check enough? Because it chains. If meeting i starts at or after i-1 ends — and that held at every earlier step too — then end$_{i-1} \le$ start$_i$, and end$_{j} \le$ start$_{j+1} \le$ start$_i$ for every earlier j, since the starts are sorted. So once no meeting clashes with its immediate predecessor, none clash at all, and a single failing neighbor is enough to prove a conflict. (Note this is about ends versus the next start — the end times themselves are not sorted, so you can’t argue from “the predecessor ends latest.”)

That turns the whole problem into one linear scan: walk the sorted list and check a single inequality at each step.

$\text{overlap}(i) \iff \text{start}_i < \text{end}_{i-1}$

The inequality is strict on purpose. A meeting that runs [0, 10] and one that runs [10, 20] are back-to-back, not overlapping — you can attend both. Using <= there would wrongly reject touching endpoints, and that’s the exact off-by-one an interviewer will probe.

Solution

Sort, then compare each meeting’s start against the previous end:

import java.util.Arrays;

class Solution {
    public boolean canAttendMeetings(int[][] intervals) {
        // Order by start time so any conflict is with the immediate neighbor.
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

        for (int i = 1; i < intervals.length; i++) {
            // This meeting begins before the previous one ends -> clash.
            if (intervals[i][0] < intervals[i - 1][1]) {
                return false;
            }
        }
        return true; // includes the empty and single-meeting cases
    }
}

Two small choices matter. Integer.compare(a[0], b[0]) instead of a[0] - b[0] avoids integer overflow when start times sit near the extremes — the subtraction trick silently breaks on large opposite-sign values. And the loop starts at i = 1, so an empty list or a lone meeting never enters it and falls straight through to true.

Complexity

Step	Time	Space
Sort	$O(n \log n)$	$O(n)$ auxiliary
Scan	$O(n)$	$O(1)$
Total	$O(n \log n)$	$O(n)$

The sort dominates the time. On space, be precise: intervals is an int[][], an array of objects, so Arrays.sort with a comparator runs TimSort, which allocates $O(n)$ temporary references — the scan itself is $O(1)$, but the sort makes the overall auxiliary space $O(n)$.

In an interview

Say the reduction out loud before you touch the keyboard: “sort by start, then a conflict can only be with the previous meeting, so it’s one pass.” That sentence is what’s being graded — it shows you saw why $O(n^2)$ was wasteful, not just that you memorized a template.

The trap they’ll poke at is the boundary: are [0, 10] and [10, 20] a conflict? Answer no, and point at the strict < in your code as the reason. If they ask what changes when you have many rooms instead of one, that’s the natural jump to Meeting Rooms II, where you count peak simultaneous meetings instead of just detecting the first clash. The same sort-then-sweep instinct also drives Merge Intervals — worth naming as you close, since the whole interval patterns cluster is really this one idea reused.

References

• LeetCode 252 — Meeting Rooms