Meeting Rooms II (Minimum Rooms Required)

Problem Statement

Given meeting intervals, return the minimum number of rooms required so that no two overlapping meetings share a room.

Example

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

Approach

Separate and sort all start times and all end times. Sweep with two pointers: when the next start is before the next end, a new meeting begins — take a room; otherwise a meeting has ended — free a room. The peak number of simultaneous rooms is the answer. (A min-heap of end times gives the same result.)

Complexity

• Time: O(n log n)
• Space: O(n)

Solution Code

Python

def minMeetingRooms(intervals):
    starts = sorted(iv[0] for iv in intervals)
    ends = sorted(iv[1] for iv in intervals)
    rooms = peak = 0
    s = e = 0
    while s < len(starts):
        if starts[s] < ends[e]:
            rooms += 1
            s += 1
            peak = max(peak, rooms)
        else:
            rooms -= 1
            e += 1
    return peak

Java

int minMeetingRooms(int[][] intervals) {
    int n = intervals.length;
    int[] starts = new int[n], ends = new int[n];
    for (int i = 0; i < n; i++) { starts[i] = intervals[i][0]; ends[i] = intervals[i][1]; }
    Arrays.sort(starts); Arrays.sort(ends);
    int rooms = 0, peak = 0, s = 0, e = 0;
    while (s < n) {
        if (starts[s] < ends[e]) { rooms++; s++; peak = Math.max(peak, rooms); }
        else { rooms--; e++; }
    }
    return peak;
}

C++

int minMeetingRooms(vector<vector<int>>& intervals) {
    int n = intervals.size();
    vector<int> starts(n), ends(n);
    for (int i = 0; i < n; i++) { starts[i] = intervals[i][0]; ends[i] = intervals[i][1]; }
    sort(starts.begin(), starts.end());
    sort(ends.begin(), ends.end());
    int rooms = 0, peak = 0, s = 0, e = 0;
    while (s < n) {
        if (starts[s] < ends[e]) { rooms++; s++; peak = max(peak, rooms); }
        else { rooms--; e++; }
    }
    return peak;
}

Key Takeaways

• Splitting starts and ends turns the problem into a simple sweep line.
• The peak concurrency equals the minimum rooms needed.
• Reference: LeetCode 253 (Meeting Rooms II).