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

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

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题速过定时计数器的结构和工作方式例题)经典例题盘点(带图解析)
|
3月前
|
人工智能 算法
第一周算法设计与分析 G : 排队援救
这篇文章介绍了解决算法问题"排队援救"的方法,通过使用队列和映射来模拟救援点的排队过程,并确定最终得到救援的人的顺序和编号。
|
6月前
|
调度
【错题集-编程题】主持人调度(一)(排序)
【错题集-编程题】主持人调度(一)(排序)
|
6月前
【错题集-编程题】活动安排(贪心 - 区间)
【错题集-编程题】活动安排(贪心 - 区间)
|
6月前
|
机器学习/深度学习 算法 测试技术
青蛙跳台阶:我如何得知它是一道斐波那契数列题?——应用题破题“三板斧”(二)
这篇内容是关于解题策略的,主要介绍了在面对应用题时可以采用的“三板斧”方法:举例、模拟和找规律。通过一个走楼梯的例子详细解释了这三个步骤如何运用。首先,举例将抽象问题具体化,比如走5级台阶有几种方式。其次,通过模拟不同情况,例如思考走每一步的可能,发现递归或循环的模式。最后,通过找规律归纳出一般性的解决方案,这里发现走台阶问题与斐波那契数列相关。文章还提到了一个拓展案例——矩形覆盖问题,同样可以用类似的方法分析。总的来说,文章强调了解题过程中理解和转化问题的重要性,以及通过训练提升这方面能力。
51 0
|
6月前
|
C语言
青蛙跳台阶:我如何得知它是一道斐波那契数列题?——应用题破题“三板斧”(一)
这篇内容介绍了C语言学习中的经典例题——斐波那契数列,强调了解题思路的重要性。斐波那契数列是一个数列,其中每个数是前两个数的和。文章指出,很多类似题目,如“青蛙跳台阶”,实质上都在考察斐波那契数列的实现。文中提供了斐波那契数列的定义、代码实现和递归与非递归的思路,并鼓励读者从问题中分析出解题模型,而非直接套用已知方法。此外,还提及了一道相关题目“矩形覆盖问题”,以供进一步练习。
47 0
|
6月前
蓝桥杯真题代码记录(最优清零方案
蓝桥杯真题代码记录(最优清零方案
55 0
【短学期算法作业】八皇后问题(回溯法)
【短学期算法作业】八皇后问题(回溯法)
【短学期算法作业】八皇后问题(回溯法)
【短学期算法作业】Kruskal算法的实现(并查集)
【短学期算法作业】Kruskal算法的实现(并查集)
【短学期算法作业】Kruskal算法的实现(并查集)