Meeting Rooms II

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

Example 1:

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

Example 2:

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

Constraints:

• 1 <= intervals.length <= 104
• 0 <= starti < endi <= 106

优先队列

我们无法按任意顺序处理给定的会议。处理会议的最基本方式是按其 开始时间 顺序排序，这也是我们采取的顺序。

排序过程很容易，但对每个会议，我们如何高效地找出是否有房间可用？任意时刻，我们都有多个可能占用的房间，只要我们能在有新会议需要时就找到一个空闲房间，我们并不需要关心到底有哪些房间是空闲的。

一个朴素的方法是，每当有新会议时，就遍历所有房间，查看是否有空闲房间。

但是,通过使用优先队列（或最小堆）堆数据结构,我们可以做得更好。

我们可以将所有房间保存在最小堆中,堆中的键值是会议的结束时间，而不用手动迭代已分配的每个房间并检查房间是否可用。

这样，每当我们想要检查有没有 任何 房间是空的，只需要检查最小堆堆顶的元素，它是最先开完会腾出房间的。

如果堆顶的元素的房间并不空闲，那么其他所有房间都不空闲。这样，我们就可以直接开一个新房间。

1. 按照 开始时间 对会议进行排序。
2. 初始化一个新的 最小堆，将第一个会议的结束时间加入到堆中。我们只需要记录会议的结束时间，告诉我们什么时候房间会空。
3. 对每个会议，检查堆的最小元素（即堆顶部的房间）是否空闲。
   1. 若房间空闲，则从堆顶拿出该元素，将其改为我们处理的会议的结束时间，加回到堆中。
   2. 若房间不空闲。开新房间，并加入到堆中。
4. 处理完所有会议后，堆的大小即为开的房间数量。这就是容纳这些会议需要的最小房间数。

代码

class Solution {
    static bool cmp(vector<int>& a, vector<int>& b){
        return a[0]<b[0];
    }
public:
    int minMeetingRooms(vector<vector<int>>& intervals) {
        priority_queue<int, vector<int>, greater<int>> q;
        sort(intervals.begin(),intervals.end(),cmp);
        int maxv = 1;//最开始是1
        for(auto& interval:intervals){
            if(!q.empty()){
                int end = q.top();q.pop();
                //如果开始时间比上一个的结束时间小，就需要新开一个房间
                //同时让上一个的结束时间重新入队
                if(interval[0]<end){
                    maxv++;
                    q.push(end);
                }
            }
            q.push(interval[1]);
        }
        return maxv;
    }
};

扫描线解题思路

开会也可以理解成坐公交，都是占用某个资源。

就拿题目给的第一组数组来分析。

intervals = [[0,30],[5,10],[15,20]]

第一个人从0上车，从30下车；

第二个人从5上车，10下车。。。

我们的问题转化为最多车上有几个人（也就是最多有多少会议室）。

显然：上车，车上人数+1；下车，车上人数-1

我们把intervals拆解一下

上车：[0, 1], [5, 1], [15, 1]

下车：[10, -1], [20, -1], [30, -1]

然后按照第一个数把上下车排好序

人数 1    2     1     2     1      0
     0----5----10----15----20-----30
变化 +1   +1    -1    +1    -1    -1

最多车上两个人。

注意：排序时，遇到一个会议结束时间和另一个会议开始时间一样的，先下车再上车。

 static bool cmp(vector<int>& a,vector<int>& b){
      //当开始和结束时间相同，要保证先下车
      int x = a[0] - b[0];
      return (x == 0 ? a[1] < b[1] : x < 0);
    }

代码

class Solution {
    static bool cmp(vector<int>& a,vector<int>& b){
      //当开始和结束时间相同，要保证先下车
      int x = a[0] - b[0];
      return (x == 0 ? a[1] < b[1] : x < 0);
    }
public:
    int minMeetingRooms(vector<vector<int>>& intervals) {
        vector<vector<int> > meetings;
        for(const vector<int>& in: intervals){
            meetings.push_back({in[0],1});
            meetings.push_back({in[1],-1});
        }
        sort(meetings.begin(),meetings.end(),cmp);
        int cnt = 0;
        int maxv = 0;
        for(const vector<int>& meet:meetings){
            cnt+=meet[1];
            maxv = max(maxv,cnt);
        }
        return maxv;
    }
};

或者使用pair<int, int>默认排序

class Solution {
  
public:
    int minMeetingRooms(vector<vector<int>>& intervals) {
 
        if (intervals.size() == 0) return 0;

        vector<pair<int, int>> meetings;
        for (const vector<int>& interval : intervals) {
            meetings.push_back({interval[0], 1});
            meetings.push_back({interval[1], -1});
        }
        sort(meetings.begin(), meetings.end());

        int cnt = 0, maxValue = 0;
        for (const pair<int, int>& meeting : meetings) {
            cnt += meeting.second;
            maxValue = max(maxValue, cnt);
        }
        return maxValue;
        
    }
};