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.

Note: The specified end time for each meeting is exclusive.

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] do not overlap with each other, so they can share a room, but [0, 30] needs a separate room since it spans the entire duration.
• Hence, 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 one room is needed to hold both meetings (at different times).

Output: 1

Solution

Split all intervals into two separate arrays — one of start times, one of end times — and sort each independently. Walk through both with two pointers: if the current start time is less than the current end time, a new meeting has begun before the earliest ongoing one finished, so increase the room count. Otherwise, a meeting has ended, so decrease it. Track the maximum room count seen at any point — that's the minimum number of rooms required.

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