题解 | #主持人调度（二）#

1.哈希表

由题可知，活动数量只会在活动开始或者活动结束的时候变化。

所以我们只需要记录这些时刻活动数量的变化值，就可以通过累加得到活动数量的变化，进而求得活动数量的最大值。

#include <climits>
#include <vector>
class Solution {
public:
    int minmumNumberOfHost(int n, vector<vector<int> >& startEnd) {
        // write code here
        map<int,int> counter;
        for(int i = 0;i<startEnd.size();++i)
        {
			//统计各个活动的时间点
            counter[startEnd[i][0]]++;
            counter[startEnd[i][1]]--;
        }
        int sum = 0;
        int res = 0;
        for(auto &r : counter)
        {
            sum += r.second;//计算当前的活动数量
            res = max(sum,res);//同一时刻最大的活动数量即所需的主持人数目
        }
        return res;
    }
};

2.优先队列

使用堆保存每个活动的结束时间，并在有新活动开始时，把已经结束的活动从堆中删除出去，再将当前活动的结束时间插入堆。

此时堆的大小即为同时存在的活动数量。

通过将所有任务按时间顺序经上述处理，当堆大小最大时，即为活动最多的时刻。

#include <climits>
#include <queue>
#include <vector>
class Solution {
public:
    int minmumNumberOfHost(int n, vector<vector<int> >& startEnd) {
        // write code here
        sort(startEnd.begin(),startEnd.end(),[](const vector<int> &a,const vector<int> &b){return a[0] < b[0];});//根据开始时间进行排序
        //优先队列，小顶堆
        priority_queue<int,vector<int>,greater<>> q;
        int res = 0;
        for(int i = 0;i<startEnd.size();++i)
        {
			//将已经结束的活动从堆中删除出去
            while(!q.empty() && startEnd[i][0] >= q.top())
                q.pop();
            q.push(startEnd[i][1]);//将当前新活动的结束时间插入队列
            res = max(res,static_cast<int>(q.size()));//获取当前最大活动数
        }
        return res;
    }
};