Meeting Rooms II

We are given an input array of meeting time intervals, intervals, where each interval has a start time and an end time. Your task is to find the minimum number of meeting rooms required to hold these meetings.

Meeting Rooms II

Problem Statement

You are given an array of meeting time intervals, intervals, where each interval has a start time and an end time. Your task is to find the minimum number of meeting rooms required to hold all the meetings.

Note: The end time for each meeting is exclusive. This means a meeting ending at time 10 and another starting at time 10 do not overlap.

Constraints

• 1 ≤ intervals.length ≤ 10³
• 0 ≤ start_i < end_i ≤ 10⁶

Examples

Example 1

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

Explanation:

• Meeting [0, 30] overlaps with both [5, 10] and [15, 20].
• [5, 10] and [15, 20] don't overlap with each other, so they can share a room. But [0, 30] needs its own room, since it spans the entire duration.
• So, 2 rooms are needed at the same time.

Output: 2

Example 2

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

Explanation:

• Meeting [2, 4] ends before meeting [7, 10] starts.
• Since the meetings don't overlap, only 1 room is needed to hold both, just at different times.

Output: 1

Solution 1: Sorting Start and End Times Separately

The idea: split all the start times and end times into two separate arrays, sort each one independently, and then walk through both using two pointers.

Steps

• We create two arrays: startTimes, holding every meeting's start time, and endTimes, holding every meeting's end time. We sort both arrays independently.
• We use two pointers, startPointer and endPointer, to walk through these sorted arrays.
• At each step, we compare the current start time with the current end time:
  • If the current start time is earlier than the current end time, it means a new meeting has begun before the earliest ongoing meeting has finished. So, we need one more room. We increase roomsNeeded, and move startPointer forward.
  • Otherwise, it means a meeting has ended, freeing up a room. We decrease roomsNeeded, and move endPointer forward.
• After each step, we update maxRooms if roomsNeeded is the highest we've seen so far.
• Once we've gone through every start time, maxRooms holds our answer — the minimum number of rooms needed at any point in time.

Code

function meetingRoomsII(intervals) {
    if (intervals.length === 0) return 0;

    // Separate and sort start times and end times independently
    const startTimes = intervals.map(([start]) => start).sort((a, b) => a - b);
    const endTimes = intervals.map(([, end]) => end).sort((a, b) => a - b);

    let roomsNeeded = 0;
    let maxRooms = 0;
    let startPointer = 0;
    let endPointer = 0;

    while (startPointer < intervals.length) {
        if (startTimes[startPointer] < endTimes[endPointer]) {
            // A meeting starts before the earliest ongoing one ends -> need another room
            roomsNeeded++;
            startPointer++;
        } else {
            // A meeting has ended -> free up a room
            roomsNeeded--;
            endPointer++;
        }
        maxRooms = Math.max(maxRooms, roomsNeeded);
    }

    return maxRooms;
}

console.log(meetingRoomsII([[7, 10], [2, 4]]));                 // 1
console.log(meetingRoomsII([[1, 10], [2, 3], [4, 5], [6, 7]])); // 2
console.log(meetingRoomsII([[0, 30], [5, 10], [15, 20]]));      // 2

Solution 2: Using a Min Heap

We can also solve this using a min heap, which keeps track of the end times of all meetings currently using a room.

Since we're only ever removing one element and adding one element at a time, the heap's size naturally tracks how many rooms are currently occupied — and if we find a room that can be reused, we remove the old end time and insert the new one, so the heap size doesn't grow unnecessarily.

Example Walkthrough

Suppose we have these meetings:

[1,5]
[2,6]
[3,4]

After processing all three, the heap holds their end times: [4, 6, 5]. This means 3 rooms are currently occupied.

Now, suppose [7,8] arrives. The heap's smallest end time is 4, and since 4 ≤ 7, that room is now free:

heap.poll(); // remove 4
heap.offer(8);

The heap now becomes [5, 6, 8] — still 3 rooms, since we reused one instead of adding a new one.

Steps

• We sort the meetings by their start time.
• We use a min heap to store the end times of meetings currently occupying a room.
• For each meeting, in order of start time:
  • We check the heap's smallest end time. If it's less than or equal to the current meeting's start time, that room has become free, so we remove that end time from the heap.
  • We then add the current meeting's end time to the heap, representing that this meeting now occupies a room (either a freed-up one, or a brand new one).
• At the end, the size of the heap tells us the maximum number of rooms that were needed at once.

Code

var minMeetingRooms = function (intervals) {
    intervals.sort((a, b) => a[0] - b[0]);

    let heap = new newHeap((a, b) => a - b);

    for (let [start, end] of intervals) {

        // Earliest room is free
        if (!heap.isEmpty() && heap.peek() <= start) {
            heap.poll();
        }

        // Occupy a room until `end`
        heap.offer(end);
    }

    return heap.size();
};