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

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

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

三、反思与改进

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


相关文章
|
1月前
|
算法 Java C语言
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-922 球员安排
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-922 球员安排
56 0
|
1月前
|
算法 Java C语言
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-675 数的划分
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-675 数的划分
32 0
|
1月前
|
算法 Java C语言
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-985 幸运的店家
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-985 幸运的店家
49 0
|
1月前
|
算法 Java C语言
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-999 数的潜能
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-999 数的潜能
50 0
|
1月前
|
算法 测试技术 C#
【贪心算法】LeetCode2071:你可以安排的最多任务数目
【贪心算法】LeetCode2071:你可以安排的最多任务数目
【期末不挂科-单片机考前速过系列P6】(第六章:10题速过定时计数器的结构和工作方式例题)经典例题盘点(带图解析)
【期末不挂科-单片机考前速过系列P6】(第六章:10题速过定时计数器的结构和工作方式例题)经典例题盘点(带图解析)
|
1月前
|
调度
【错题集-编程题】主持人调度(一)(排序)
【错题集-编程题】主持人调度(一)(排序)
|
1月前
【错题集-编程题】活动安排(贪心 - 区间)
【错题集-编程题】活动安排(贪心 - 区间)
|
1月前
|
Java C语言 C++
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-150 6-1 递归求二项式系数值
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-150 6-1 递归求二项式系数值
47 1
|
1月前
|
机器学习/深度学习 算法 Java
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-659 比赛安排
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-659 比赛安排
33 0