Meeting Rooms
EasyIntervals
You get a list of meetings, each written as [start, end]. Return true if one person could attend all of them, meaning no two overlap, and false otherwise.
A meeting that starts at the very moment another ends does not overlap it: [1, 3] and [3, 5] can both be attended. The meetings are not given in any particular order.
Examples
Input: intervals = [[9, 11], [13, 15], [11, 12]] Output: true
In time order: 9 to 11, 11 to 12, 13 to 15. The second starts just as the first ends.
Input: intervals = [[2, 5], [8, 10], [4, 7]] Output: false
The meeting from 4 to 7 starts before the one from 2 to 5 is over.
Constraints
0 ≤ intervals.length ≤ 10⁴0 ≤ start < end ≤ 10⁶
Stuck?
Hint 1
Once the meetings are sorted by start time, any clash shows up between two neighbours.
Hint 2
Sort by start, then check that each meeting starts no earlier than the one before it ends. Mind the equal case: touching is allowed.
The idea
Sort the meetings by start time. Then any clash shows up between two neighbours. If each meeting starts no earlier than the one before it ends, every meeting is over before the next begins, so meetings further apart cannot clash either.
Time O(n log n)Extra space O(1) besides the sort
Try it again with the idea in mind, or go through the code one step at a time.
The code, step by step
Step 1 of 4
Sort a copy by start time, so the caller's array is left as it was. The comparator a[0] - b[0] sorts by number; sort() without one would compare as text.
function canAttendMeetings(intervals) { const sorted = [...intervals].sort((a, b) => a[0] - b[0]); for (let i = 1; i < sorted.length; i++) { if (sorted[i][0] < sorted[i - 1][1]) return false; } return true;}The trap
Writing the overlap test with <= feels like the careful choice. Here it is wrong: a meeting that starts at the very moment the previous one ends does not overlap it. Back-to-back meetings that share an end time and a start time get reported as a clash.
function canAttendMeetings(intervals) { const sorted = [...intervals].sort((a, b) => a[0] - b[0]); for (let i = 1; i < sorted.length; i++) { if (sorted[i][0] <= sorted[i - 1][1]) return false; // treats touching meetings as a clash } return true;}