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

**Example 1:**

```
Input: [[0, 30],[5, 10],[15, 20]]
Output: 2
```

**Example 2:**

```
Input: [[7,10],[2,4]]
Output: 1
```

```cpp
// Treemap
int minMeetingRooms(vector<vector<int>>& intervals) { // time: O(nlogn); space: O(n)
    map<int, int> m;
    for (vector<int>& i : intervals) {
        ++m[i[0]];
        --m[i[1]];
    }
    int cur = 0, res = 0;
    for (auto& e : m) {
        cur += e.second;
        res = max(res, cur);
    }
    return res;
}
```

```cpp
// Sort + Greedy
int minMeetingRooms(vector<vector<int>>& intervals) { // time: O(nlogn); space: O(n)
    if (intervals.empty()) return 0;
    sort(intervals.begin(), intervals.end());
    priority_queue<int, vector<int>, greater<int> > pq; // min heap
    pq.push(intervals[0][1]); // first end
    for (int i = 1; i < intervals.size(); ++i) {
        if (intervals[i][0] >= pq.top()) pq.pop();
        pq.push(intervals[i][1]);
    }
    return pq.size();
}
```

```cpp
// Sort
int minMeetingRooms(vector<vector<int>>& intervals) { // time: O(nlogn); space: O(n)
    vector<pair<int, int> > v;
    for (const vector<int>& i : intervals) {
        v.push_back({i[0], 1});
        v.push_back({i[1], -1});
    }
    sort(v.begin(), v.end());
    int cur = 0, res = 0;
    for (pair<int, int>& p : v) {
        cur += p.second;
        res = max(res, cur);
    }
    return res;
}
```

{% content-ref url="252.-meeting-rooms" %}
[252.-meeting-rooms](252.-meeting-rooms)
{% endcontent-ref %}
