> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/array_and_numbers/sao-miao-xian/meeting-rooms-ii.md).

# 253. Meeting Rooms II

> 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

```cpp
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的大小也就是所需会议室数目。

```java
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).