【错题集-编程题】主持人调度（二）（贪心 + 优先级队列）

本文主要是介绍【错题集-编程题】主持人调度（二）（贪心 + 优先级队列），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

牛客对应题目链接：主持人调度（二）_牛客题霸_牛客网 (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();}
};

---

三、反思与改进

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

这篇关于【错题集-编程题】主持人调度（二）（贪心 + 优先级队列）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---