253. Meeting Rooms II

https://leetcode.com/problems/meeting-rooms-ii/description/

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), find the minimum number of conference rooms required.

For example,

Given [[0, 30],[5, 10],[15, 20]],

return 2.

Thoughts

给一系列区间，问最多重合的区间数。start和end分别当做两个时间点，根据时间点排序后，从左往右依次当遇到start就+1, 遇到end就-1求和。区间重合时数目即此时sum的值。 当start和另一点的end重合时, end排在前面因为要先出来。

Code

class Solution {
public:
    int minMeetingRooms(vector<vector<int>>& intervals) {
        vector<vector<int>> ts;
        for (const auto &interval : intervals) {
            ts.push_back({interval[0], 1});
            ts.push_back({interval[1], -1});
        }
        sort(ts.begin(), ts.end(), [](const auto &a, const auto &b) {
           return a[0] == b[0] ? a[1] < b[1] : a[0] < b[0]; 
        });
        int sum = 0, res = 0;
        for (const auto &t : ts) {
            sum += t[1];
            res = max(res, sum);
        }
        return res;
    }
};

还可以针对startTime对Intervals排好序，并用一个min heap模拟所需要的会议室，heap里存每个会议室要用到的时间(endTime)。对intervals遍历，并和min heap首元素作对比，当大于或等于时，说明有会议室空了出来，把首抛出。再让当前会议的endTime入pq。最后pq的大小也就是所需会议室数目。

class Solution {
public:
    int minMeetingRooms(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), [](const auto &a, const auto &b) {
           return a[0] < b[0];
        });
        priority_queue<int, vector<int>, greater<int>> pq;
        for (const auto &interval : intervals) {
            if (!pq.empty() && pq.top() <= interval[0]) pq.pop();
            pq.push(interval[1]);
        }
        return pq.size();
    }
};

Analysis

时间复杂度O(NlgN).