首页 > 试题广场 >

主持人调度（二）

[编程题]主持人调度（二）
  • 热度指数：71271 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
有 n 个活动即将举办，每个活动都有开始时间与活动的结束时间，第 i 个活动的开始时间是 starti ,第 i 个活动的结束时间是 endi ,举办某个活动就需要为该活动准备一个活动主持人。

一位活动主持人在同一时间只能参与一个活动。并且活动主持人需要全程参与活动，换句话说，一个主持人参与了第 i 个活动，那么该主持人在 (starti,endi) 这个时间段不能参与其他任何活动。求为了成功举办这 n 个活动，最少需要多少名主持人。

数据范围: ， -2^{32} \le start_i\le end_i \le 2^{31}-1

复杂度要求：时间复杂度 ，空间复杂度
示例1

输入

2,[[1,2],[2,3]]

输出

1

说明

只需要一个主持人就能成功举办这两个活动
示例2

输入

2,[[1,3],[2,4]]

输出

2

说明

需要两个主持人才能成功举办这两个活动

备注:
start_i,end_i在int范围内
算法知识视频讲解
开通博客
头像 牛客题解官
发表于 2022-04-22 13:08:53
精华题解 题目的主要信息： n个活动，有各自的区间 一个主持人不能在相交的区间工作 将相交的区间分成一组，最后组数即是主持人的数量 数字为int型的范围，可能会出现负数 举一反三： 学习完本题的思路你可以解决如下题目： BM89. 合并区间 BM95. 分糖果问题 方法一：排序+遍历比较（推荐使用） 知识 展开全文
去ta的博客 赞 (35) 回复(1) 收起
头像 iterator
发表于 2021-07-31 00:47:28
主持人调度 描述有n个活动即将举办，每个活动都有活动的开始时间与活动的结束时间，第i个活动的开始时间是,第i个活动的结束时间是,举办某个活动就需要为该活动准备一个活动主持人。一位活动主持人在同一时间只能参与一个活动。并且活动主持人需要全程参与活动，换句话说，活动主持人参与了第i个活动，那么该主持 展开全文
去ta的博客 赞 (38) 回复(3) 收起
头像 xqxls
发表于 2021-07-26 16:49:26
题意整理 有n个活动即将举办，每个活动都有一个开始时间和结束时间。 现在派若干个主持人来主持活动，要求每一个主持人主持的活动中，各个活动的时间段（开始时间到结束时间）不重叠。 方法一（优先队列） 1.解题思路 首先对startEnd按开始时间从小到大排序，如果开始时间相同，则按结束时间排序。 展开全文
去ta的博客 赞 (18) 回复(3) 收起
头像 LifelongCode
发表于 2021-02-08 22:57:02
解法1：优先级队列 首先：要对活动进行排序： 开始时间相等的，结束时间从小到大 开始时间不相等的，开始时间从小到大 其次：建立一个优先级队列：默认升序，同时处理活动 只提供结束时间，如果当前的开始时间小于队首的结束时间，说明没空闲 如果当前的开始时间大于队首的结束时间，说明可以空闲一个，队首出 展开全文
去ta的博客 赞 (13) 回复(4) 收起
头像 wkkw
发表于 2021-10-31 10:46:12
说实话开始没做出来。就是没想到怎么转换，甚至别人的题解开始都没看懂，看了好几遍。 换种思路来考虑这个问题。 寻找题目的规律，假设全部活动安排好了，主持人也根据题目的情况刚好到位了。寻找第N个活动的情况跟前N-1个活动的关系。 问题： 1.第N个活动是否需要新增主持人。 展开全文
去ta的博客 赞 (11) 回复(0) 收起
头像 潦草急就
发表于 2021-07-27 10:45:27
差分数组（详见力扣1893），题目等同于求当前位置最大被多少个区间包围。 class Solution { public: int minmumNumberOfHost(int n, vector<vector<int> >& startEnd) { 展开全文
去ta的博客 赞 (6) 回复(0) 收起
头像 什么大肥猪
发表于 2022-06-21 15:30:23
package main import "sort" /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * 计算成功举办活动需要多少名主持人 * @param n int整型 有n个活动 * @param startEnd int整型二维数组 sta 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 牛客347614775号
发表于 2021-12-30 19:18:42
//循环超时。则把问题拆分解决 function minmumNumberOfHost( n , startEnd ) { // write code here let star=[] let end=[] let host=0 for(let i=0;i& 展开全文
去ta的博客 赞 (2) 回复(5) 收起
头像 小洋芋热爱NLP
发表于 2021-08-13 00:09:53
- 题目描述：- 题目链接： https://www.nowcoder.com/practice/4edf6e6d01554870a12f218c94e8a299?tpId=196&&tqId=37562&rp=1&ru=/activity/oj&qru=/t 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 啊展是啊这
发表于 2022-03-29 12:56:16
边界计数法 import java.util.*; public class Solution { public int minmumNumberOfHost (int n, int[][] startEnd) { // Arrays.sort(startEnd, (a, 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 wuqg5518
发表于 2021-10-18 16:54:18
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * 计算成功举办活动需要多少名主持人 * @param n int整型 有n个活动 展开全文
去ta的博客 赞 (1) 回复(0) 收起

问题信息

贪心
难度：
75条回答 5837浏览

热门推荐

通过挑战的用户

查看代码

相关试题

主持人调度（二）

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号