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

简介: 【错题集-编程题】主持人调度(二)(贪心 + 优先级队列)

f47889f806c04e128e51ba36c038f42a.png

一、分析题目

把区间按照左端点排序,然后搞个堆:

  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();
    }
};

三、反思与改进

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


相关文章
|
6月前
|
算法 测试技术 C#
【贪心算法】LeetCode2071:你可以安排的最多任务数目
【贪心算法】LeetCode2071:你可以安排的最多任务数目
【期末不挂科-单片机考前速过系列P6】(第六章:10题速过定时计数器的结构和工作方式例题)经典例题盘点(带图解析)
【期末不挂科-单片机考前速过系列P6】(第六章:10题速过定时计数器的结构和工作方式例题)经典例题盘点(带图解析)
|
6月前
|
调度
【错题集-编程题】主持人调度(一)(排序)
【错题集-编程题】主持人调度(一)(排序)
|
6月前
【错题集-编程题】活动安排(贪心 - 区间)
【错题集-编程题】活动安排(贪心 - 区间)
|
6月前
|
存储
【错题集-编程题】组队竞赛(排序 + 贪心)
【错题集-编程题】组队竞赛(排序 + 贪心)
|
6月前
|
算法 Java C语言
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1006 拿金币
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1006 拿金币
66 0
|
6月前
|
移动开发 算法 Java
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-998 娜神平衡
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-998 娜神平衡
59 0
|
6月前
|
算法 Java C语言
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-基础练习 杨辉三角形(最好的基础题,没有之一)
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-基础练习 杨辉三角形(最好的基础题,没有之一)
39 0
|
算法 网络架构
代码随想录算法训练营第三十三天 | LeetCode 1005. K 次取反后最大化的数组和、134. 加油站、135. 分发糖果
代码随想录算法训练营第三十三天 | LeetCode 1005. K 次取反后最大化的数组和、134. 加油站、135. 分发糖果
55 0
【短学期算法作业】八皇后问题(回溯法)
【短学期算法作业】八皇后问题(回溯法)
【短学期算法作业】八皇后问题(回溯法)