Meeting Rooms II

Examples

Input: intervals = [[0,30],[5,10],[15,20]]
Output: 2

[0,30] overlaps both [5,10] and [15,20], but [5,10] and [15,20] don't overlap each other, so 2 rooms are enough.

Input: intervals = [[7,10],[2,4]]
Output: 1

These meetings never overlap, so they can share a single room.

Input: intervals = [[1,5],[8,9],[8,9]]
Output: 2

The two [8,9] meetings happen at the exact same time, so they each need their own room.

Constraints

• 1 <= intervals.length <= 10^4

• intervals[i].length == 2

• 0 <= start < end <= 10^6

Approach

A direct way to find the busiest moment is: for every meeting's start time, count how many meetings are actually in progress right then (start <= t < end), and keep the largest count you see across all of them. That's the minimum number of rooms.

The faster approach separates all the start times and all the end times into two sorted lists, and sweeps through them like a timeline of events. Walk the start times in order; each time you're about to admit a new meeting, first check whether an earlier meeting has already ended by then — if so, that room is free and can be reused, so no new room is needed. Otherwise, you need to open a new room. Tracking the running count of rooms in use (and its peak) as you sweep gives you the answer in one pass over the sorted events.

Solutions

Brute Force — Count Active Meetings at Each Start Time

For every meeting's start time, scan the whole list and count how many meetings are actually in progress at that moment (their start is at or before it, and their end is after it). The largest count found across all start times is the number of rooms needed, since that's the busiest instant.

function minMeetingRooms(intervals) {
  let maxRooms = 0;

  for (let i = 0; i < intervals.length; i++) {
    const t = intervals[i][0];
    let count = 0;
    for (let j = 0; j < intervals.length; j++) {
      if (intervals[j][0] <= t && t < intervals[j][1]) {
        count++;
      }
    }
    maxRooms = Math.max(maxRooms, count);
  }

  return maxRooms;
}

Time: O(n^2) — for every meeting, rescan all meetings · Space: O(1) extra space

Optimal — Sweep Sorted Starts and Ends

Split the meetings into two separate sorted arrays: all the start times and all the end times. Now walk through the start times in order with one pointer, and the end times in order with another pointer.

At each step, compare the current start against the earliest end still outstanding. If the start comes before that end, a brand-new room is needed right now (increment rooms in use). If the start is at or after that end, some earlier meeting has already finished, so that room can be reused instead (decrement rooms in use, and move to the next end). Track the highest "rooms in use" value seen — that peak is the answer.

function minMeetingRooms(intervals) {
  const n = intervals.length;
  if (n === 0) return 0;

  const starts = intervals.map((iv) => iv[0]).sort((a, b) => a - b);
  const ends = intervals.map((iv) => iv[1]).sort((a, b) => a - b);

  let roomsInUse = 0;
  let maxRooms = 0;
  let startPtr = 0;
  let endPtr = 0;

  while (startPtr < n) {
    if (starts[startPtr] < ends[endPtr]) {
      roomsInUse++;
      startPtr++;
    } else {
      roomsInUse--;
      endPtr++;
    }
    maxRooms = Math.max(maxRooms, roomsInUse);
  }

  return maxRooms;
}

Time: O(n log n) — dominated by sorting the starts and ends · Space: O(n) for the two sorted arrays