Meeting Rooms
Problem
Given an array of meeting time intervals where intervals[i] = [start_i, end_i], determine if a person could attend all meetings without any overlaps.
- 0 ≤ intervals.length ≤ 10⁴
- intervals[i].length == 2
- 0 ≤ start_i < end_i ≤ 10⁶
Example
intervals = [[0,30],[5,10],[15,20]]falseSorting intervals by start time yields [[0,30],[5,10],[15,20]]. The first interval ends at 30, which overlaps with the second interval starting at 5, so the person cannot attend all meetings.
Approach
Straightforward Solution
A brute-force approach compares every pair of intervals to check for overlaps, resulting in O(n^2) time complexity, which is inefficient for large inputs.
Core Observation
If any two meetings overlap, the person cannot attend both. Overlaps occur when the start time of a meeting is less than the end time of the previous meeting when intervals are sorted by start time.
Path to Optimal
Sorting intervals by their start times arranges meetings chronologically. Then, a single linear scan comparing each meeting's start time with the previous meeting's end time detects overlaps efficiently. This reduces the problem from O(n^2) to O(n log n) due to sorting.
Optimal Approach
Sort the intervals by start time. Iterate through the sorted list, and for each interval, check if its start time is less than the end time of the previous interval. If so, return false immediately. If no overlaps are found, return true after the iteration.
Time
O(n log n)
Sorting the intervals dominates the runtime at O(n log n). The subsequent linear scan is O(n), which does not increase the overall complexity.
Space
O(1)
The sorting can be done in-place, and only a constant amount of extra space is used for variables during iteration.
Pattern Spotlight
Greedy Algorithms (Interval Scheduling Overlap Detection)
Sorting intervals by start time reveals overlaps through a single linear pass, enabling immediate detection of conflicts by comparing adjacent intervals without backtracking or complex data structures.
Solution
| 1 | class Solution:
|
| 2 | def canAttendMeetings(self, intervals: list[list[int]]) -> bool:
|
| 3 | intervals.sort(key=lambda i: i[0])
|
| 4 |
|
| 5 | for i in range(1, len(intervals)):
|
| 6 | i1 = intervals[i-1]
|
| 7 | i2 = intervals[i]
|
| 8 |
|
| 9 | if i1[1] > i2[0]:
|
| 10 | return False
|
| 11 |
|
| 12 | return True |
Step-by-Step Solution
Sort Intervals by Start Time to Establish Chronological Order
| 3 | intervals.sort(key=lambda i: i[0])
|
Objective
To arrange all meetings in ascending order of their start times, enabling efficient overlap detection.
Key Insight
Sorting intervals by start time transforms the problem into a linear scan for overlaps. This ordering guarantees that any conflicting meetings will be adjacent, eliminating the need for nested comparisons.
Interview Quick-Check
Core Logic
Sorting by start time ensures that overlapping intervals appear consecutively, allowing a single pass to detect conflicts.
Complexity
Sorting takes O(n log n) time, which is the bottleneck of the algorithm.
Detect Overlaps by Comparing Adjacent Intervals
| 5 | for i in range(1, len(intervals)):
|
| 6 | i1 = intervals[i-1]
|
| 7 | i2 = intervals[i]
|
| 9 | if i1[1] > i2[0]:
|
| 10 | return False
|
Objective
To identify any conflicting meetings by checking if the current meeting starts before the previous meeting ends.
Key Insight
After sorting, the only possible overlaps occur between consecutive intervals. Comparing the end time of the previous interval with the start time of the current interval reveals conflicts immediately, allowing early termination.
Interview Quick-Check
Core Logic
If the end time of the previous interval is greater than the start time of the current interval, an overlap exists and the answer is false.
State & Boundaries
The loop starts from the second interval (index 1) because the first interval has no previous interval to compare.
Common Pitfalls & Bugs
Failing to sort before this step can cause missed overlaps or incorrect results.
Return True if No Overlaps Are Found After Full Scan
| 12 | return True |
Objective
To confirm that all meetings can be attended by returning true when no conflicts are detected.
Key Insight
If the iteration completes without finding any overlapping intervals, it guarantees that the schedule is conflict-free, so the person can attend all meetings.
Interview Quick-Check
Core Logic
Returning true after the loop confirms no overlaps were found in the sorted intervals.
Line Analysis
This solution has 2 Critical lines interviewers watch for.
if i1[1] > i2[0]:Check if the previous meeting ends after the current meeting starts, indicating an overlap.
This condition detects the critical conflict where two meetings overlap in time, making it impossible to attend both.
intervals.sort(key=lambda i: i[0])Sort the intervals in ascending order based on their start times.
Sorting by start time arranges meetings chronologically, which is essential for detecting overlaps efficiently by comparing only adjacent intervals.
return FalseReturn false immediately upon detecting an overlap.
Early termination upon finding any overlap improves efficiency by avoiding unnecessary checks once a conflict is confirmed.
return TrueReturn true if no overlaps are found after checking all intervals.
Completing the loop without returning false guarantees that all meetings are non-overlapping and can be attended.
for i in range(1, len(intervals)):Iterate through intervals starting from the second one.
Starting from index 1 allows comparison of each interval with its immediate predecessor to detect overlaps.
i1 = intervals[i-1]Assign the previous interval to a variable for clarity.
Storing the previous interval simplifies the overlap comparison and improves code readability.
i2 = intervals[i]Assign the current interval to a variable for clarity.
Storing the current interval separately makes the overlap condition more explicit and easier to understand.
Test Your Understanding
Why is sorting intervals by start time sufficient to detect all overlaps with a single pass?
Because sorting arranges intervals chronologically, any overlap must occur between adjacent intervals in the sorted order. Non-adjacent intervals cannot overlap without overlapping an intermediate interval, so checking adjacent pairs is sufficient.
Related Problems
Greedy pattern
Don't just read it. Drill it.
Reconstruct Meeting Rooms from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Meeting Rooms drill