253. Meeting Rooms II

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, cnt = 0;
        for (int i = 0, j = 0; i < N;) {
            if (starts[i] < ends[j]) {
                ++cnt;
                ++i;
                ans = max(ans, cnt);
            } else if (starts[i] > ends[j]) {
                --cnt;
                ++j;
            } else {
                ++i;
                ++j;
            }
        }
        return ans;
    }
};

Solution 2.

// 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 3. 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) {
        int N = A.size(), ans = 0;
        sort(begin(A), end(A));
        auto cmp = [&](int a, int b) { return A[a][1] > A[b][1]; };
        priority_queue<int, vector<int>, decltype(cmp)> pq(cmp); 
        for (int i = 0; i < N; ++i) {
            int start = A[i][0];
            while (pq.size() && A[pq.top()][1] <= start) pq.pop();
            pq.push(i);
            ans = max(ans, (int)pq.size());
        }
        return ans;
    }
};