牛客对应题目链接：主持人调度（二）_牛客题霸_牛客网 (nowcoder.com)

---

一、分析题目

把区间按照左端点排序，然后搞个堆：

1. 先把第⼀个区间的右端点加⼊到堆中。
2. 遍历后⾯的区间，分情况讨论：（1）如果左端点大于等于堆顶元素，能接在后面，干掉堆顶，然后把这个区间的右端点加⼊堆。（2）否则，只能再来⼀个人，只把这个区间的右端点加⼊堆。
3. 最后堆的大小就是需要的⼈数

---

二、代码

//O(NlogN)
class Solution
{
public:
    int minmumNumberOfHost(int n, vector<vector<int> >& startEnd) 
    {
        sort(startEnd.begin(), startEnd.end());
        priority_queue<int, vector<int>, greater<int>> heap; // 创建⼀个⼩根堆
        heap.push(startEnd[0][1]); // 先把第⼀个区间放进去

        for(int i = 1; i < n; i++) // 处理剩下的区间
        {
            int a = startEnd[i][0], b = startEnd[i][1];
            if(a >= heap.top()) // 没有重叠
            {
                heap.pop();
                heap.push(b);
            }
            else // 有重叠
            {
                heap.push(b); // 重新安排⼀个⼈
            }
        }
        return heap.size();
    }
};

---

三、反思与改进

对优先级队列掌握的还不够熟悉，导致想不起可以用这个容器来解决问题。因为主持人可以主持多场活动，所以不能直接遍历比较。