# 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).


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://hao-fu-1.gitbook.io/oj/array_and_numbers/sao-miao-xian/meeting-rooms-ii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.