LeetCode 252 · Easy · Intervals

Meeting Rooms

Given meeting times as [start, end], decide whether one person could attend all of them, so that no two meetings overlap. A meeting may start the moment another ends.

O(n log n)time · the sort
O(1)extra space
sort by startcheck neighbours

0–8 meetings · [start,end] with 0 ≤ start < end ≤ 30 · any order

Number line meetings sorted by start · bottom lane: your calendar, one room · the line marks i1.end

public boolean canAttendMeetings(List<Interval> intervals) { intervals.sort((a, b) -> Integer.compare(a.start, b.start)); for (int i = 1; i < intervals.size(); i++) { Interval i1 = intervals.get(i - 1); Interval i2 = intervals.get(i); if (i1.end > i2.start) { // overlap return false; } } return true;}
i
—
i1
—
i2
—

Why it works

  1. Brute force checks every pair of meetings for overlap: O(n²) comparisons.
  2. After sorting by start, only neighbours can clash first. If meeting i clears meeting i − 1, it also clears every earlier one, because those all ended by the time i − 1 started. So one pass over adjacent pairs decides it.
  3. Cost: O(n log n) for the sort, then n − 1 comparisons. The sort is in place, so O(1) extra space (List.sort is a merge sort, TimSort, which may use O(n) scratch).
  4. Pitfall: use a strict >. [1,3] then [3,6] is back to back, not a clash. And an empty list, or a single meeting, is attendable.
  5. Follow-up: Meeting Rooms II (253) asks how many rooms you need when meetings may overlap: sweep the starts and ends and track the peak.