Meeting Rooms
Problem
Given an array of meeting time intervals [start, end), decide whether one person could attend every meeting — that is, no two meetings overlap.
Sort by start time, then sweep: a conflict appears the first time intervals[i].start < intervals[i − 1].end.
intervals = [[0,30],[5,10],[15,20]]falsedef can_attend(intervals):
intervals.sort(key=lambda iv: iv[0])
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;
}
}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;
}Explanation
One person can attend every meeting only if no two meetings overlap. The simplest way to check that is to sort meetings by start time and then look at neighbors.
Once sorted, any conflict must show up between adjacent meetings, because if meeting i starts before the previous one ends, they clash. So we just test intervals[i][0] < intervals[i-1][1] for each consecutive pair.
The moment we find such an overlap we return false. If we get all the way through with no overlap, the answer is true.
Example: [[0,30],[5,10],[15,20]] sorts to the same order. Comparing [5,10] against [0,30], we see 5 < 30, an overlap, so the answer is false.
Sorting is what makes the single neighbor check sufficient, so the whole job is one sort plus one linear scan.