Meeting Rooms
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. 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. If we sort the meetings by start time, we only need to check consecutive meetings for overlap. When every consecutive pair is conflict-free, each meeting starts at or after the previous one ends, and chaining those inequalities shows that any meeting also starts at or after every earlier meeting ends. So a single conflict anywhere in the list always shows up as a conflict between some adjacent pair.
Key Constraints:
0 <= intervals.length <= 10^4→ With n up to 10,000, an O(n^2) brute force checks up to 50 million pairs, which is slow. An O(n log n) sorting approach handles this size comfortably.0 <= start_i < end_i <= 10^6→ Start is always strictly less than end, so every meeting has a positive duration. There are no zero-length or inverted intervals to handle. The values fit in a 32-bit integer, so overflow is not a concern.
Approach 1: Brute Force
Intuition
Compare every pair of meetings and check whether they overlap. Two meetings [s1, e1] and [s2, e2] overlap when each starts before the other ends, which is the condition s1 < e2 and s2 < e1. If any pair satisfies it, a person cannot attend both, so the answer is false.
This checks n*(n-1)/2 pairs, so it gets slow as the list grows, but it needs no sorting and works as a baseline.
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.
The brute force checks many pairs that cannot possibly conflict. Sorting the meetings into chronological order removes that waste, because then only neighboring meetings need to be compared.
Approach 2: Sorting
Intuition
Sorting the meetings by start time guarantees that any conflict surfaces between two adjacent meetings. After sorting, each meeting only needs to be compared against the one right before it: if the current meeting starts before the previous one ends, that is an overlap. A single pass through the sorted array settles the question.
Checking only adjacent pairs is enough. Suppose, after sorting by start time, every adjacent pair is conflict-free, so end[i-1] <= start[i] for all i. For any two meetings j < k, chaining those inequalities gives end[j] <= start[j+1] <= ... <= start[k], so meeting k starts after meeting j ends and they do not overlap. A conflict between any two meetings therefore forces a conflict between some adjacent pair, which the single pass detects.
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).