题解 | #主持人调度#

优先队列（小根堆）：用于存储每个主持人主持的最后一场活动的结束时间，堆中元素个数就是主持人的个数

1. 将所有区间先按照开始时间从小到大排序，对于开始时间相等的按照结束时间排序

2. 遍历所有区间

   • 每次判断当前区间的开始时间是否大于堆顶的结束时间，如果大于等于，那么这场活动可以和堆顶这场活动使用同一个主持人，所以把堆顶弹出；否则如果小于，那么两场活动不能同时主持，还需要一个主持人
   • 将当前区间的结束时间入堆

3. 最后堆中元素个数就是需要的主持人个数。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 计算成功举办活动需要多少名主持人
     * @param n int整型 有n个活动
     * @param startEnd int整型vector<vector<>> startEnd[i][0]用于表示第i个活动的开始时间，startEnd[i][1]表示第i个活动的结束时间
     * @return int整型
     */
    int minmumNumberOfHost(int n, vector<vector<int> >& startEnd) {
        sort(startEnd.begin(), startEnd.end(), [](vector<int>& s1, vector<int>& s2){
            if (s1[0] == s2[0]) return s1[1] < s2[1];
            return s1[0] < s2[0];
        });
        
        priority_queue<int, vector<int>, greater<int>> heap;
        for (auto item : startEnd) {
            if (heap.size() && heap.top() <= item[0]) {
                heap.pop();
            }
            heap.push(item[1]);
        }
        
        return heap.size();
    }
};