Meeting Rooms
Understand the problem
Given a list of meetings intervals, each being [start, end]. Question: can one person attend all the meetings (no two overlap)? Return true/false.
Examples:
intervals = [[0, 30], [5, 10], [15, 20]]
output = false // [5,10] overlaps [0,30]
intervals = [[7, 10], [2, 4]]
output = trueMeetings that touch at the edge ([1,5] and [5,8]) do NOT count as overlapping — the earlier one ends just as the next one begins.
Show the basic approach (slower)
O(n²) time, O(1) spacefunction canAttendMeetings(intervals: number[][]): boolean {
for (let i = 0; i < intervals.length; i++) {
for (let j = i + 1; j < intervals.length; j++) {
const [s1, e1] = intervals[i]
const [s2, e2] = intervals[j]
if (s1 < e2 && s2 < e1) return false // overlap
}
}
return true
}Compare every pair of meetings to see whether they overlap.
Correct but costly — for large n, n² comparisons are wasteful, because after sorting you only need to compare adjacent meetings.
Optimal solution
O(n log n) time, O(1) spacefunction canAttendMeetings(intervals: number[][]): boolean {
intervals.sort((a, b) => a[0] - b[0]) // by start time ascending
for (let i = 1; i < intervals.length; i++) {
if (intervals[i][0] < intervals[i - 1][1]) {
return false // this meeting starts before the previous one ends
}
}
return true
}The optimal solution sorts the meetings by start time; after that, any overlap must happen between two adjacent meetings — there is no need to compare every pair.
Just check whether the next meeting starts earlier than the previous one ends.
Step-by-step trace
1function canAttendMeetings(intervals: number[][]): boolean {2 intervals.sort((a, b) => a[0] - b[0]) // by start time ascending3 for (let i = 1; i < intervals.length; i++) {4 if (intervals[i][0] < intervals[i - 1][1]) {5 return false // this meeting starts before the previous one ends6 }7 }8 return true9}Edge cases to remember
Touching edges
[1,5],[5,8]: use<(not<=) when comparing start with prevEnd, so 5 < 5 is false → attendable, as required.An empty list or exactly 1 meeting → always true (nothing to overlap with).
Input not sorted by time — you must sort first, otherwise comparing adjacent meetings gives wrong results.
Several meetings with the same start ([2,4],[2,5]) → 2 < 4 → false.