Meeting Rooms
Last Updated: March 29, 2026
Understanding the Problem
We're given a list of meetings, each with a start and end time, and we need to figure out if any two meetings overlap. If they do, a person can't attend all of them, so we return false. If no meetings overlap, we return true.
Two meetings overlap when one starts before the other ends. Think about it on a timeline: if meeting A runs from 1 to 5 and meeting B runs from 3 to 7, there's a conflict between time 3 and 5. The key observation is that if we sort the meetings by start time, we only need to check consecutive meetings for overlap. Why? Because if meetings are sorted and meeting B doesn't overlap with meeting A, then any meeting starting after B can't overlap with A either.
Key Constraints:
0 <= intervals.length <= 10^4→ With n up to 10,000, an O(n^2) brute force (checking every pair) would mean up to 100 million comparisons. That's borderline but likely too slow. An O(n log n) sorting approach is safe and efficient.0 <= start_i < end_i <= 10^6→ Start is always strictly less than end, so every meeting has a positive duration. We don't need to handle zero-length meetings or inverted intervals.
Approach 1: Brute Force
Intuition
The most direct approach: compare every pair of meetings and check if they overlap. Two meetings [s1, e1] and [s2, e2] overlap if one starts before the other ends and vice versa. Formally, they overlap if s1 < e2 and s2 < e1.
This is what you'd do if someone handed you a list of meetings on paper. You'd go through each pair one by one and check for conflicts. It works, but it's slow because you're checking n*(n-1)/2 pairs.
Algorithm
- For each meeting at index
i, compare it with every meeting at indexj > i. - Two meetings overlap if
intervals[i][0] < intervals[j][1]andintervals[j][0] < intervals[i][1]. - If any pair overlaps, return
false. - If no overlapping pair is found, return
true.
Example Walkthrough
Code
- Time Complexity: O(n^2). We check every pair of meetings. With n meetings, there are n*(n-1)/2 pairs, each requiring O(1) to compare.
- Space Complexity: O(1). No extra data structures needed. We only use a couple of loop variables.
This works but checks many unnecessary pairs. What if we arranged the meetings in chronological order so we only need to check each meeting against its neighbor?
Approach 2: Sorting
Intuition
Here's the key insight: if we sort the meetings by start time, overlapping meetings must be adjacent in the sorted order. Think about why. If meeting A starts at time 2 and meeting C starts at time 10, any meeting B that starts between them (say at time 5) would appear between A and C after sorting. So if A overlaps with C, it definitely overlaps with B too (since B starts earlier than C).
This means after sorting, we only need to check each meeting against the one right before it. If the current meeting starts before the previous one ends, we have an overlap. One pass through the sorted array and we're done.
Sorting brings order to chaos. Before sorting, overlapping meetings could be anywhere in the array, so you'd need to check every pair. After sorting by start time, overlapping meetings are guaranteed to be next to each other. This is because if meeting A starts before meeting B (after sorting), and meeting C starts after meeting B, then if A doesn't overlap B, A can't possibly overlap C either (C starts even later).
So the overlap check reduces from "compare everything with everything" to "compare each meeting with just its predecessor." That's the power of sorting in interval problems.
Algorithm
- Sort the intervals by their start time.
- Iterate through the sorted intervals starting from index 1.
- For each meeting, check if its start time is less than the previous meeting's end time.
- If yes, return
false(overlap detected). - If we finish the loop without finding any overlap, return
true.
Example Walkthrough
Code
- Time Complexity: O(n log n). Sorting takes O(n log n). The single pass to check consecutive meetings takes O(n). The sorting step dominates, giving us O(n log n) overall.
- Space Complexity: O(1) to O(n). Depends on the sorting algorithm. In-place sorts like heapsort use O(1) extra space. Java's Arrays.sort for objects uses a modified mergesort with O(n) space. The overlap check itself uses O(1).