meeting-rooms-ii

253. Meeting Rooms II

Given an array of meeting time intervals intervals where intervals[i] = [starti, endi], return the minimum number of conference rooms required.

Example 1:

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

Example 2:

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

Constraints:

• 1 <= intervals.length <= 104
• 0 <= starti < endi <= 106

class Solution {
public:
    int minMeetingRooms(vector<vector<int>>& intervals) {
        int n = intervals.size();

        sort(intervals.begin(), intervals.end());
        priority_queue<int, vector<int>, greater<int>> minHeap;

        // #0: minHeap = [30];
        // #1: minHeap = [10, 30];
        // #2: minHeap = [10, 20];
        for (auto& interval : intervals) {
            if (!minHeap.empty() && interval[0] >= minHeap.top()) {
                minHeap.pop();
            }
            minHeap.push(interval[1]);
        }
        return minHeap.size();
    }
};

• T: $O(N \log N)$
• S: $O(N)$