Meeting Rooms
Sort by start — if any meeting begins before the previous one ends, the schedule conflicts.
2 min read
intervals sorting
Problem#
Return true iff a person can attend all given meetings (i.e., no two overlap).
Examples#
[[0,30],[5,10],[15,20]]→false.[[7,10],[2,4]]→true.
Constraints#
0 <= intervals.length <= 10^4.
Approach#
Sort by start. Walk pairwise: if any meeting starts before the previous one ends, conflict.
Solution#
class Solution {public: bool canAttendMeetings(vector<vector<int>>& intervals) { sort(intervals.begin(), intervals.end()); for (int i = 1; i < (int)intervals.size(); ++i) if (intervals[i][0] < intervals[i-1][1]) return false; return true; }};import "sort"
func canAttendMeetings(intervals [][]int) bool { sort.Slice(intervals, func(i, j int) bool { return intervals[i][0] < intervals[j][0] }) for i := 1; i < len(intervals); i++ { if intervals[i][0] < intervals[i-1][1] { return false } } return true}from typing import List
class Solution: def canAttendMeetings(self, intervals: List[List[int]]) -> bool: intervals.sort() for i in range(1, len(intervals)): if intervals[i][0] < intervals[i - 1][1]: return False return Truefunction canAttendMeetings(intervals) { intervals.sort((a, b) => a[0] - b[0]); for (let i = 1; i < intervals.length; i++) { if (intervals[i][0] < intervals[i - 1][1]) return false; } return true;}class Solution { public boolean canAttendMeetings(int[][] intervals) { Arrays.sort(intervals, (a, b) -> a[0] - b[0]); for (int i = 1; i < intervals.length; i++) { if (intervals[i][0] < intervals[i - 1][1]) return false; } return true; }}function canAttendMeetings(intervals: number[][]): boolean { intervals.sort((a, b) => a[0] - b[0]); for (let i = 1; i < intervals.length; i++) { if (intervals[i][0] < intervals[i - 1][1]) return false; } return true;}Editorial#
After sorting by start, consecutive intervals are the only candidates to conflict — non-adjacent intervals are “blocked” by the one between. The strict < matches “touching but not overlapping” being OK.
Complexity#
- Time:
O(n log n). - Space:
O(1).
Concept revision#
Related#