252. Meeting Rooms
Model: qwen2.5-coder:14b
Topics: Sort
FAANG asked: 1
Acceptance rate: 55.5%
Problem Breakdown
The problem asks us to determine if a person can attend all meetings given an array of meeting time intervals. Each interval is represented as [starti, endi], where starti is the start time and endi is the end time of the meeting. The input is an array of these intervals, and the output should be a boolean indicating whether it’s possible to attend all meetings without any overlap.
Inputs:
- An array of intervals, where each interval is
[starti, endi].
Outputs:
- A boolean value (
trueorfalse) indicating if all meetings can be attended without overlapping.
Implicit Constraints/Edge Cases:
- If the input list is empty, the person trivially can attend all meetings (return
true). - The intervals are non-negative and within a specified range.
- There might be multiple intervals with the same start or end time, but they should not overlap unless one ends exactly when another starts.
Intuition
A brute-force approach would involve checking every pair of intervals to see if they overlap. This would result in a time complexity of O(n^2), which is inefficient for large inputs. The key insight is that if we sort the intervals by their start times, we only need to check adjacent intervals for overlaps. Sorting takes O(n log n) time, and checking adjacent intervals takes O(n) time, making this approach more efficient.
Approach
- Sort the Intervals: First, sort the array of intervals based on their start times. This allows us to easily check for overlapping meetings by comparing each interval with the next one in the sorted list.
- Check for Overlaps: Iterate through the sorted intervals and compare the end time of the current interval with the start time of the next interval. If the end time of the current interval is greater than the start time of the next interval, it means there is an overlap, and we return
false. - Return True if No Overlaps: If no overlaps are found after checking all adjacent intervals, return
true.
Complexity Analysis
- Time Complexity: O(n log n) due to the sorting step, where n is the number of intervals.
- Space Complexity: O(1) additional space (excluding the input and output), as we only use a few extra variables.
Solution
def canAttendMeetings(intervals):
# Sort intervals by start time
intervals.sort(key=lambda x: x[0])
# Check for overlapping intervals
for i in range(len(intervals) - 1):
if intervals[i][1] > intervals[i + 1][0]:
return False
return True
Edge Cases Handled
- Empty Input: The function returns
truebecause there are no meetings to attend, so trivially all can be attended. - Single Interval: The function handles this by returning
true, as a single meeting does not overlap with itself. - Adjacent Meetings: If one meeting ends exactly when another starts (e.g.,
[1, 2]and[2, 3]), the function correctly returnstruebecause they do not overlap.