LeetCode 252 · LeetCode 253 · Intervals · Heap

Meeting Rooms

MediumCan one person attend every meeting (252) — and how many rooms are needed (253)?
Given an array of meeting time intervals where intervals[i] = [start, end]: (252) determine if a person could attend all meetings — i.e. no two overlap. (253) Return the minimum number of conference rooms required to hold all the meetings. (End is treated as exclusive: [5,10] and [10,15] do not conflict.)

Walkthrough

try:
Each [start, end] is a meeting on a shared time axis. End is exclusive — [5,10] and [10,15] do not clash.
problem:
M00,30M15,10M215,20030
previouscurrent / conflict
1
function canAttendMeetings(intervals) {
2
  intervals.sort((a, b) => a[0] - b[0]);
◄
3
  for (let i = 1; i < intervals.length; i++) {
4
    if (intervals[i][0] < intervals[i - 1][1]) {
5
      return false;
6
    }
7
  }
8
  return true;
9
}
step 0 / 2
line 2
Sort by start time
Line them up in the order they begin. Then a conflict can only happen between neighbours.

Intuition

Sort the meetings by start time. Once sorted, you only ever have to think about how a meeting relates to the ones already in progress.

252 — Can attend all? After sorting, an overlap can only occur between back-to-back neighbours. If any meeting starts before its predecessor ends, the answer is false.

253 — Minimum rooms? Keep a min-heap of the END times of meetings currently using a room. The smallest end is the soonest a room frees up.

For each meeting, if the soonest-ending room is already free (its end ≤ this start), reuse it (pop); then add this meeting’s end. The number of rooms is the most that are ever in the heap at once.

The algorithm

  1. 01Sort the intervals by start time.
  2. 02252: scan neighbours — if intervals[i].start < intervals[i-1].end, return false; else return true.
  3. 03253: keep a min-heap of end times; for each meeting, pop if heap.peek() ≤ start, then push the end.
  4. 04253: the heap size never shrinks below its peak — that peak is the answer.

Reference implementations

252 · Can attend all? — sort + neighbour check

Sort by start, then a single pass: if any meeting begins before the previous one ends, they overlap. O(n log n) time, O(1) extra space.

1
function canAttendMeetings(intervals) {
2
  intervals.sort((a, b) => a[0] - b[0]);
3
  for (let i = 1; i < intervals.length; i++) {
4
    if (intervals[i][0] < intervals[i - 1][1]) {
5
      return false;     // starts before the previous meeting ends
6
    }
7
  }
8
  return true;
9
}
253 · Minimum rooms — sort + min-heap

Sort by start and keep a min-heap of end times. Reuse the soonest-freeing room when possible; the peak heap size is the rooms needed. This is the version animated above.

1
function minMeetingRooms(intervals) {
2
  intervals.sort((a, b) => a[0] - b[0]);
3
  const heap = new MinHeap();        // end times of meetings in progress
4
  for (const [start, end] of intervals) {
5
    if (heap.size() > 0 && heap.peek() <= start) {
6
      heap.pop();                    // earliest meeting ended; reuse its room
7
    }
8
    heap.push(end);
9
  }
10
  return heap.size();
11
}

Complexity

Time
O(n log n) — dominated by the sort (the heap operations are O(n log n) total).
Space
O(n) for the heap (252 needs only O(1) beyond the sort).