DSA
Meeting Rooms
Intervals. Time O(N * logN), Space O(N).
PatternIntervals (Sort + Merge)OptimalO(N * logN) time · O(N) space
Solve on LeetCode Key insighttry it first, then reveal
Two meetings conflict if and only if one starts before the other ends.
Given an array of meeting time intervals consisting of start and end times [(s1,e1),(s2,e2),...] (si < ei), determine if a person could attend all meetings.
Approach#
- Intuition: Two meetings conflict if and only if one starts before the other ends. After sorting by start time, any conflict will always be between two adjacent intervals — a later interval can only conflict with the one immediately before it in sorted order, never with one further back.
- Mechanics: Sort the intervals by start time. Then scan linearly; if any interval's start time is strictly less than the previous interval's end time, a conflict exists and the person cannot attend all meetings.
- Trade-off: Sorting reduces an O(n²) pairwise comparison problem to an O(n log n) sort followed by a single O(n) pass. No extra data structure is needed beyond the sort itself.
cpp
bool canAttendMeetings(vector<vector<int>> &intervals)
{
sort(intervals.begin(), intervals.end());
for(int i=1;i<intervals.size();i++)
{
if(intervals[i][0] < intervals[i-1][1])
return false;
}
return true;
}
Time Complexity: O(N * logN)
Space Complexity: O(N)