#252 Meeting Rooms
the problem
In plain words
Each meeting is [start, end): it takes the time from start up to, but not including, end. Can one person attend all of them? A meeting that ends at 10 and one that starts at 10 don't clash.
in intervals = [[0,30],[5,10],[15,20]]
out false
[0,30] clashes with both of the others.
in intervals = [[7,10],[2,4]]
out true
- 0 ≤ intervals.length ≤ 10⁴
- 0 ≤ start < end ≤ 10⁶
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code right here. Stuck for 20 minutes? Open one hint at a time.
This one is LeetCode Premium. You don't need a subscription: solve it right here. The free alternative linked above is the closest free practice; its label says how close it is.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternInterval merging (sort by start)
After sorting by start, if any two meetings clash, then some neighbouring pair clashes. So one sort and one comparison per neighbour is enough.
solutions
From brute force to optimal
Two meetings clash when each starts before the other ends. Check all pairs.
- For every pair (i, j): if a[0] < b[1] and b[0] < a[1], return false.
- Return true.
n(n − 1)/2 pairs.
No extra structures.
class Solution { public boolean canAttendMeetings(int[][] intervals) { for (int i = 0; i < intervals.length; i++) { for (int j = i + 1; j < intervals.length; j++) { int[] a = intervals[i], b = intervals[j]; if (a[0] < b[1] && b[0] < a[1]) return false; // [start, end) clash } } return true; }}Sort by start. Each meeting must start at or after the previous one ends.
- Sort a copy by start.
- For i ≥ 1: if sorted[i][0] < sorted[i − 1][1], return false.
- Return true.
The sort dominates; the scan is O(n).
The sorted copy (sort in place to need only the sort's own memory).
class Solution { public boolean canAttendMeetings(int[][] intervals) { int[][] sorted = intervals.clone(); // keep the caller's order Arrays.sort(sorted, (a, b) -> Integer.compare(a[0], b[0])); for (int i = 1; i < sorted.length; i++) { if (sorted[i][0] < sorted[i - 1][1]) return false; // starts before the previous one ends } return true; }}in the room
How to say it in the interview
talk track
- Clarify: do [5,10] and [10,15] clash? (No.)
- Sort by start. Explain why a clash anywhere shows up between two neighbours: the meeting right after any meeting starts earliest.
- Code the neighbour check with
<.
traps
- Using
<=: then back-to-back meetings wrongly clash. - Comparing each meeting with the previous one without sorting first.
what they ask next
Follow-ups
If they can't all be attended, how many rooms do you need?
That's Meeting Rooms II (LC 253), later in this chapter: the maximum overlap at any moment.
before you submit
Edge cases to test
- No meetings → true.
- [[5,10],[10,15]] → true: touching isn't a clash.
- A short meeting inside a long one, [[1,5],[2,3]] → false.
practise next
Similar problems
- #253Meeting Rooms IIMediumin IntervalsLeetCode Premium
- #56Merge IntervalsMediumin Intervals