题目描述

Given an array of meeting time intervals intervals where intervals[i] = [starti, endi], return the minimum number of conference rooms required.

样例

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

Input: intervals = [[7,10],[2,4]]
Output: 1

数据范围

1 <= intervals.length <= 10^4
0 <= starti < endi <= 10^6

算法1

(排序) $O(n\log n)$

基本思路是贪心：当有空闲会议室可以用时，我们用空闲会议室而不开新会议室；反之若先前的会议室都被占用，我们别无选择只能新开会议室。

为了方便考虑，我们用物理的思想去分析问题，按照物理时间从小到大去考虑重要的时间点

分开考虑开始时间和结束时间，遍历原序列，将每个会议的起始时间和结束时间分别存入st, ed数组中，并分别排序

用指针i, j分别维护会议的开始时间和结束时间，初始i = 0, j = 0, ans = 0

只要遇到一个新的开始时间，我们先不管别的，总是开一个新的会议室，即令ans ++，然后我们看一下能否将当前这个会议安排到之前的某个会议室中。考察当前开始时间st[i]和结束时间ed[j]的大小关系，若st[i] >= ed[j]，说明当前会议开始时刻有一个空闲会议室，我们令ans --，同时更新当前维护的会议结束时间，即令j ++

时间复杂度

需要$O(n\log n)$的时间分别对开始时间和结束时间排序，然后用$O(n)$的时间遍历两个序列维护答案。

C++ 代码

class Solution {
public:
    int minMeetingRooms(vector<vector<int>>& intervals) {
        vector<int> st, ed;
        for(auto& x : intervals)
        {
            st.push_back(x[0]);
            ed.push_back(x[1]);
        }
        sort(st.begin(), st.end());
        sort(ed.begin(), ed.end());
        int res = 0, n = st.size();
        for(int i = 0, j = 0; i < n && j < n; i ++)
        {
            if(st[i] >= ed[j]) res --, j ++;
            res ++;
        }
        return res;
    }
};

算法2

(堆) $O(n\log n)$

类似的思路，我们将原序列按照会议开始时间排序，并维护一个小根堆存会议的结束时间

初始将第一个会议的结束时间加入堆中，答案res = 1，然后枚举所有会议，若当前枚举到的会议开始时间小于堆顶，说明这两个会议时间冲突，需要开新的会议室，同时将当前会议的结束时间加入堆中；若当前会议的开始时间大于堆顶，说明当前会议可以安排在原来堆顶会议的会议室中，此时弹出堆顶，将当前会议加入堆中

时间复杂度

需要$O(n\log n)$的时间排序，然后线性扫描，每次扫描中都要常数次堆操作。总的时间复杂度为$O(n\log n)$

C++ 代码

class Solution {
public:
    int minMeetingRooms(vector<vector<int>>& intervals) {
        priority_queue<int, vector<int>, greater<int>> heap;
        sort(intervals.begin(), intervals.end());
        heap.push(intervals[0][1]);
        int res = 1;
        for(int i = 1; i < intervals.size(); i ++)
        {
            auto t = heap.top();
            if(intervals[i][0] < t)
                res ++;
            else heap.pop();
            heap.push(intervals[i][1]);
        }
        return res;
    }
};