题目描述

给你一个会议时间安排的数组 intervals ，每个会议时间都会包括开始和结束的时间 intervals[i] = [starti, endi] ，为避免会议冲突，同时要考虑充分利用会议室资源，请你计算至少需要多少间会议室，才能满足这些会议安排。

样例

输入：intervals = [[0,30],[5,10],[15,20]]
输出：2

输入：intervals = [[7,10],[2,4]]
输出：1

算法1

(扫描线，差分) $O(nlogn)$

类似AcWing 906. 区间分组，可以认为一个组内可以承接不冲突的区间，然后求最小组的数量,可以转化为这道题的做法。
区别:906题不允许端点重合，本题允许端点重合。

从题意出发，早开始的先排，按左端点排序(相同时，右端点排在左端点前面)，会议室数量遇到左端点+1，右端点-1，统计的会议室不同时刻需要的最大值。

时间复杂度分析：O(nlogn)

C++ 代码

class Solution {
public:
    int minMeetingRooms(vector<vector<int>>& intervals) {
        vector<pair<int,int>> lis;
        for(auto& v:intervals){
            lis.push_back({v[0],1});
            lis.push_back({v[1],-1});
        }
        sort(lis.begin(),lis.end());
        int ans = 0;
        int sum = 0;
        for(auto &v:lis){
            sum+= v.second;
            ans = max(ans, sum);
        }
        return ans;
    }
};

算法2

(优先队列) $O(nlogn)$

一个会议如果能使用之前的会议室，那么就使用，不然就另外开一个会议室，如果使用的话，当然使用结束时间最早的会议室，所以优先队列存储的会议室的结束时间，使用小根堆。会议遍历时，要从最早开始的会议开始，所以先按左端点排序。

时间复杂度分析：O(nlogn)

C++ 代码

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