253

253. Meeting Rooms II (Medium)

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

Companies:
Amazon, Facebook, Bloomberg, Microsoft, Google, Oracle, Walmart Labs, ByteDance, Uber, Twitter, Snapchat, Yahoo, VMware, Quora, Visa, Swiggy

Related Topics:
Array, Two Pointers, Greedy, Sorting, Heap (Priority Queue)

Similar Questions:

• Merge Intervals (Medium)
• Meeting Rooms (Easy)
• Minimum Number of Arrows to Burst Balloons (Medium)
• Car Pooling (Medium)

Solution 1.

// OJ: https://leetcode.com/problems/meeting-rooms-ii/
// Author: github.com/lzl124631x
// Time: O(NlogN)
// Space: O(N)
class Solution {
public:
    int minMeetingRooms(vector<vector<int>>& A) {
        vector<int> starts, ends;
        for (auto &v : A) {
            starts.push_back(v[0]);
            ends.push_back(v[1]);
        }
        sort(begin(starts), end(starts));
        sort(begin(ends), end(ends));
        int N = A.size(), ans = 0;
        for (int i = 0, j = 0; i < N; ++ans, ++i) {
            if (starts[i] < ends[j]) continue;
            --ans;
            ++j;
        }
        return ans;
    }
};

Solution 2. Heap

// OJ: https://leetcode.com/problems/meeting-rooms-ii/
// Author: github.com/lzl124631x
// Time: O(NlogN)
// Space: O(N)
class Solution {
public:
    int minMeetingRooms(vector<vector<int>>& A) {
        sort(begin(A), end(A), [](auto &a, auto &b) { return a[0] != b[0] ? a[0] < b[0] : a[1] < b[1]; });
        int ans = 0;
        priority_queue<int, vector<int>, greater<>> pq; // min heap of end times
        for (auto &v : A) {
            int s = v[0], e = v[1];
            while (pq.size() && pq.top() <= s) pq.pop();
            pq.push(e);
            ans = max(ans, (int)pq.size());
        }
        return ans;
    }
};