一位活动主持人在同一时间只能参与一个活动。并且活动主持人需要全程参与活动，换句话说，一个主持人参与了第 i 个活动，那么该主持人在 (starti,endi) 这个时间段不能参与其他任何活动。求为了成功举办这 n 个活动，最少需要多少名主持人。
数据范围:
复杂度要求：时间复杂度 )
，空间复杂度 )
[编程题]主持人调度（二）
- 热度指数：71271 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
- 算法知识视频讲解
有 n 个活动即将举办，每个活动都有开始时间与活动的结束时间，第 i 个活动的开始时间是 starti ,第 i 个活动的结束时间是 endi ,举办某个活动就需要为该活动准备一个活动主持人。
一位活动主持人在同一时间只能参与一个活动。并且活动主持人需要全程参与活动，换句话说，一个主持人参与了第 i 个活动，那么该主持人在 (starti,endi) 这个时间段不能参与其他任何活动。求为了成功举办这 n 个活动，最少需要多少名主持人。
数据范围:
， 
一位活动主持人在同一时间只能参与一个活动。并且活动主持人需要全程参与活动，换句话说，一个主持人参与了第 i 个活动，那么该主持人在 (starti,endi) 这个时间段不能参与其他任何活动。求为了成功举办这 n 个活动，最少需要多少名主持人。
数据范围:
示例1
输入
2,[[1,2],[2,3]]
输出
1
说明
只需要一个主持人就能成功举办这两个活动
示例2
输入
2,[[1,3],[2,4]]
输出
2
说明
需要两个主持人才能成功举办这两个活动
备注:
在int范围内
将活动开始时间写入一个列表starts，进行排序。
将活动结束时间写入一个列表ends，进行排序。
每次活动开始时，需要增加一个主持人上场，每次活动结束时候可以释放一个主持人。
所以按照时间先后顺序对starts进行遍历，每次有活动开始count++，每次有活动结束count--
在count最大的时候，即是需要主持人最多的时候
class Solution: def minmumNumberOfHost(self , n , startEnd ): starts=[] ends=[] for start,end in startEnd: starts.append(start); ends.append(end); starts.sort(); ends.sort() i,j,count,res=0,0,0,0 for time in starts: while(i<n and starts[i]<=time): i+=1 count+=1 while(j<n and ends[j]<=time): j+=1 count-=1 if res<count: res=count return res
编辑于 2021-06-14 23:18:19
回复(10)
python 问题类比于：同一时间最多重叠区间个数
class Solution: def minmumNumberOfHost(self , n , startEnd ): # 问题类比于 同一时间最多有多少个重叠区间 # 分别统计活动的开始时间和结束时间 start = [] end = [] for host in startEnd: start.append(host[0]) end.append(host[1]) start.sort() end.sort() # 统计同一时间的活动个数 count = 0 max_num = 0 # 活动索引号 i, j = 0, 0 while i < n and j < n: # 有新活动开始 if start[i] < end[j]: # 转到下个活动的开始时间作对比 i += 1 count += 1 # 记录过程中的最大个数 max_num = max(max_num, count) # 一个活动开始同时一个活动结束 elif start[i] == end[j]: i += 1 j += 1 # 一个活动结束 else: # 转到下个活动的结束时间作对比 j += 1 count -= 1 # 返回最大值(同一时间最多有多少个活动在举行) return max_num
发表于 2021-07-24 15:17:12
回复(0)
首先将每个主持任务按开始时间和结束时间升序进行二次排序，然后遍历任务数组。这样就是按时间线来进行遍历，且对于开始时间相同的主持任务，优先选择时间短的，这样才更可能“连轴转”，紧接着做下一个主持任务。接下来可以用小根堆模拟排队过程。
建立一个小根堆存储主持任务的结束时间，意味着可以在O(1)的时间复杂度内知道哪个主持任务能够最早结束，遍历到某个任务时：(1) 如果小根堆的堆顶小于等于当前任务的开始时间，说明做堆顶任务的主持人此时是空闲的，可以把当前主持任务揽下来，因此不需要增加主持人，把堆顶任务弹出，当前任务入堆；(2) 如果小根堆的堆顶大于当前任务的开始时间，这就说明这个最早能“收工”的主持人都没空接下当前任务，堆顶下面任务的主持人当然就更没空了，所以此时不出堆，新任务的结束时间直接入堆，表示需要增加一个主持人。
按时间线遍历下来之后，堆中有几个任务积压，就说明至少需要多少个主持人。
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 计算成功举办活动需要多少名主持人
* @param n int整型 有n个活动
* @param startEnd int整型二维数组 startEnd[i][0]用于表示第i个活动的开始时间，startEnd[i][1]表示第i个活动的结束时间
* @return int整型
*/
public int minmumNumberOfHost (int n, int[][] startEnd) {
// write code here
Arrays.sort(startEnd, new Comparator<int[]>(){
@Override
public int compare(int[] task1, int[] task2){
if(task1[0] != task2[0]){
return task1[0] < task2[0]? -1: 1;
}else{
return task1[1] < task2[1]? -1: 1;
}
}
});
PriorityQueue<Integer> pq = new PriorityQueue<>(); // 用于存储刚结束活动的end时间
pq.offer(startEnd[0][1]);
for(int i = 1; i < n; i++){
if(startEnd[i][0] >= pq.peek()){
// 有空闲不需要增加主持人，当前主持人可以紧接着干下一个活
pq.poll(); // 把上一个活出队，当前活会入队
}
pq.offer(startEnd[i][1]); // 如果跟上一个活时间重叠，就直接入队
}
return pq.size(); // 队列中积压的元素数量就是需要的主持人数
}
}
发表于 2021-12-12 10:25:59
回复(3)
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 计算成功举办活动需要多少名主持人
* @param n int整型 有n个活动
* @param startEnd int整型vector<vector<>> startEnd[i][0]用于表示第i个活动的开始时间，startEnd[i][1]表示第i个活动的结束时间
* @return int整型
*/
int minmumNumberOfHost(int n, vector<vector<int> >& startEnd) {
// 时间复杂度O(NlogN)，空间复杂度O(N)
const int N = startEnd.size();
int start[N], end[N];
for (int i = 0; i < N; ++i) {
start[i] = startEnd[i][0];
end[i] = startEnd[i][1];
}
sort(start, start + n);
sort(end, end + n);
int j = 0, res = 0;
for (int i = 0; i < N; ++i) {
if (start[i] >= end[j]) ++j;
else ++res;
}
return res;
}
};
发表于 2022-10-19 16:47:48
回复(0)
class Solution: def minmumNumberOfHost(self , n: int, startEnd: List[List[int]]) -> int: ''' 思路: 解题思路 正在进行的活动数量只会在 各活动开始或结束时变化. 对正在进行的活动计数. ''' # 首先由开始时间排序. startEnd.sort(key=lambda x:x[0]) # 利用辅助数组，给每个活动的时间节点 标记start 或者 end. date = [] for i in range(n): date.append([startEnd[i][0], 'start']) date.append([startEnd[i][1], 'end']) # 再给date排序 date.sort(key=lambda x:x[0]) # 计数, 从左至右遍历时间轴，start标签则num++, end则num-- # res即当num最大时. res = 0; num = 0 for d in date: if d[1] == 'start': num += 1 elif d[1] == 'end': num -= 1 res = max(num, res) return res
发表于 2022-05-21 20:46:41
回复(1)
int minmumNumberOfHost(int n, vector<vector<int> >& startEnd) {
// write code here
if (n == 1) return 1;
map<int, int> cnt; // 有序
for (auto& vec : startEnd) {
++cnt[vec[0]];
--cnt[vec[1]];
}
int ans = 0;
int curFreq = 0;
for (auto& [_, freq] : cnt) {
curFreq += freq;
ans = max(ans, curFreq);
}
return ans;
} 差分数组
发表于 2022-08-06 19:06:32
回复(1)
from heapq import * class Solution: def minmumNumberOfHost(self , n: int, startEnd: List[List[int]]) -> int: # write code here pq = [] startEnd.sort() for i in range(len(startEnd)): if len(pq)>0 and pq[0]<=startEnd[i][0]: heappop(pq) heappush(pq,startEnd[i][1]) return len(pq)
发表于 2021-12-11 16:30:05
回复(0)
class Solution: def minmumNumberOfHost(self , n: int, startEnd: List[List[int]]) -> int: # write code here sort_startend = sorted(startEnd, key = lambda x:x[0]) hosts =[] for it in sort_startend: if len(hosts)>0 and it[0] >= hosts[0]: heappop(hosts) heappush(hosts,it[1]) return len(hosts)
发表于 2023-12-19 23:24:21
回复(0)
图片来自HHHChen77，在此致谢！！！
startTime和endTime分别排序后，使用双指针，类似合并有序链表/数组的思想
如果有活动开始，count++；有活动结束，count--；既有活动开始又有活动结束，count不动
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 计算成功举办活动需要多少名主持人
* @param n int整型 有n个活动
* @param startEnd int整型二维数组 startEnd[i][0]用于表示第i个活动的开始时间，startEnd[i][1]表示第i个活动的结束时间
* @return int整型
*/
public int minmumNumberOfHost (int n, ArrayList<ArrayList<Integer>> startEnd) {
// write code here
int[] startTime = new int[n];
int[] endTime = new int[n];
for (int i = 0; i < n; i++) {
startTime[i] = startEnd.get(i).get(0);
endTime[i] = startEnd.get(i).get(1);
}
Arrays.sort(startTime);
Arrays.sort(endTime);
int res = 0;
int i = 0, j = 0, count = 0;
while (i < n && j < n) {
if (startTime[i] < endTime[j]) {
count++;
i++;
} else if (startTime[i] > endTime[j]) {
count--;
j++;
} else {
// startTime[i] == endTime[j]
i++;
j++;
}
res = Math.max(res, count);
}
return res;
}
}
发表于 2022-09-19 23:31:21
回复(1)
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 计算成功举办活动需要多少名主持人
* @param n int整型 有n个活动
* @param startEnd int整型ArrayList<ArrayList<>> startEnd[i][0]用于表示第i个活动的开始时间，startEnd[i][1]表示第i个活动的结束时间
* @return int整型
*/
public int minmumNumberOfHost (int n, int[][] startEnd) {
// write code here
//ArrayList<ArrayList<Integer>>
int[] start=new int[n];
int[] end=new int[n];
for(int i=0;i<=n-1;i++){
// start[i]=startEnd.get(i).get(0);
// end[i]=startEnd.get(i).get(1);
start[i]=startEnd[i][0];
end[i]=startEnd[i][1];
}
Arrays.sort(start);
Arrays.sort(end);
int host=1;
int j=0;
for(int i=1;i<=n-1;++i){
if(start[i]>=end[j]){
j++;
}else{
host++;
}
}
return host;
}
}
发表于 2022-08-25 15:01:28
回复(0)
# # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # 计算成功举办活动需要多少名主持人 # @param n int整型 有n个活动 # @param startEnd int整型二维数组 startEnd[i][0]用于表示第i个活动的开始时间，startEnd[i][1]表示第i个活动的结束时间 # @return int整型 # class Solution: def minmumNumberOfHost(self , n: int, startEnd: List[List[int]]) -> int: # write code here ## 分离 开始时间和结束时间 start和end start = [i[0] for i in startEnd] end = [i[1] for i in startEnd] ## 排序 ：如果有交叉，则就需要加一个主持人 start.sort() end.sort() ## 使用一个循环控制两个数组 num = 0 end_time = 0 for i in range(n): if start[i] >= end[end_time]: end_time += 1 ## 无交叉情况，后移end_time else: num += 1 ## 有交叉，主持人数量 + 1 return num
发表于 2022-07-21 10:49:07
回复(2)
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 计算成功举办活动需要多少名主持人
* @param n int整型 有n个活动
* @param startEnd int整型vector<vector<>> startEnd[i][0]用于表示第i个活动的开始时间，startEnd[i][1]表示第i个活动的结束时间
* @return int整型
*/
int minmumNumberOfHost(int n, vector<vector<int> >& startEnd) {
// write code here
// 按开始时间从小到大排序开始时间相同，按结束时间从小到大排序。
sort(startEnd.begin(), startEnd.end(), [](auto& a, auto& b){
if (a[0] == b[0]) return a[1] < b[1];
return a[0] < b[0];
});
priority_queue<int, vector<int>, greater<int>> q;
int ans = 0;
for (int i = 0; i < n; ++i) {
//当前开始时间大等于先前最早结束活动时间，不用添加新的主持人
if (!q.empty() && startEnd[i][0] >= q.top()) {
q.pop();
}
// 否则添加新的主持人主持活动
else ++ans;
// 添加或更新一个新的结束时间
q.push(startEnd[i][1]);
}
return ans;
}
};
发表于 2022-05-12 18:34:14
回复(0)
class Solution {
public:
int minmumNumberOfHost(int n, vector<vector<int> >& startEnd) {
if(startEnd.empty()) return 0;
sort(startEnd.begin(),startEnd.end(),[](vector<int>& a,vector<int>& b){
if(a[0]!=b[0])
return a[0] < b[0];//按照活动开始时间升序排序
else
return a[1] < b[1];//活动开始时间相等的，按照活动结束时间排序
});
//排序后，越靠前的活动都是尽早开始尽早结束
//用小顶堆存储活动的结束时间，每当有一个新的任务来时，如果这个任务的开始时间>=堆顶的最早结束时间，则主持人数目不变，反之主持人+1
priority_queue<int,vector<int>,greater<int> > min_q;
min_q.push(startEnd[0][1]);
for(int i=1;i<n;i++){
if(startEnd[i][0]>=min_q.top()) {// 有空闲不需要增加主持人，当前主持人可以紧接着干下一个活
min_q.pop();// 把上一个活出队，当前活会入队，即更新当前主持人赶下一个活的结束时间
}
min_q.push(startEnd[i][1]);// 如果跟上一个活时间重叠，就直接入队
}
return min_q.size();
}
};
发表于 2022-05-12 12:30:48
回复(0)
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 计算成功举办活动需要多少名主持人
* @param n int整型 有n个活动
* @param startEnd int整型二维数组 startEnd[i][0]用于表示第i个活动的开始时间，startEnd[i][1]表示第i个活动的结束时间
* @return int整型
*/
public int minmumNumberOfHost (int n, int[][] startEnd) {
Arrays.sort(startEnd, (a, b) -> a[0] <= b[0] ? -1 : 1);
PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();
int ans = 0;
for (int[] interval : startEnd) {
while (!minHeap.isEmpty() && interval[0] >= minHeap.peek()) {
minHeap.poll();
}
minHeap.add(interval[1]);
ans = Math.max(ans, minHeap.size());
}
return ans;
}
}
发表于 2022-02-28 12:05:03
回复(0)
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 计算成功举办活动需要多少名主持人
* @param n int整型 有n个活动
* @param startEnd int整型vector<vector<>> startEnd[i][0]用于表示第i个活动的开始时间，startEnd[i][1]表示第i个活动的结束时间
* @return int整型
*/
int minmumNumberOfHost(int n, vector<vector<int> >& startEnd) {
// write code here
map<int, int> mp;
for (const auto& item : startEnd) {
mp[item[0]]++;
mp[item[1]]--;
}
int cur = 0;
int ret = 0;
for (const auto& item : mp) {
cur += item.second;
if (cur > ret) ret = cur;
}
return ret;
}
};
发表于 2021-09-04 00:23:55
回复(0)
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
# 计算成功举办活动需要多少名主持人
# @param n int整型 有n个活动
# @param startEnd int整型二维数组 startEnd[i][0]用于表示第i个活动的开始时间，startEnd[i][1]表示第i个活动的结束时间
# @return int整型
#
class Solution:
def minmumNumberOfHost(self , n , startEnd ):
start=[]
end=[]
for i in range(n):
start.append(startEnd[i][0])
end.append(startEnd[i][1])
start.sort()
end.sort()
count=0
j=0
for i in range(n):
if start[i]>=end[j]:
j+=1
else:
count+=1
return count
# write code here
发表于 2021-05-13 11:21:38
回复(0)
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 计算成功举办活动需要多少名主持人
* @param n int整型 有n个活动
* @param startEnd int整型二维数组 startEnd[i][0]用于表示第i个活动的开始时间，startEnd[i][1]表示第i个活动的结束时间
* @return int整型
*/
function dealData(startArr,endArr) {
let maxCount = 0
let temCount = 0
for (let i = 0; i < startArr.length; i++) {
temCount += 1
const item1 = startArr[i]
for(let j=0;j<endArr.length;j++){
if(endArr[j] <= item1){
temCount -= 1
endArr.shift()
}else{
break
}
}
if(temCount > maxCount) maxCount = temCount
}
return maxCount
}
export function minmumNumberOfHost(n: number, startEnd: number[][]): any {
const startArr = [];
const endArr = [];
for (let i = 0; i < startEnd.length; i++) {
const item = startEnd[i];
startArr.push(item[0]);
endArr.push(item[1]);
}
startArr.sort((a, b) => a - b);
endArr.sort((a, b) => a - b);
return dealData(startArr,endArr)
// console.log({startArr,endArr})
// return {startArr,endArr}
}
发表于 2024-12-02 10:12:33
回复(0)
这题目有歧义吧 同时开始同时结束也算一个活动吧 也要分配一个人去主持吧 难道1,[123,123]这个用例输出0？
发表于 2024-10-31 20:58:56
回复(0)
问题信息
难度：
75条回答
912收藏
5825浏览
通过挑战的用户
查看代码-
2023-03-14 12:15:24
-
2023-03-13 16:58:17
-
2023-02-26 11:03:29
-
2023-02-23 17:06:37
-
2023-02-19 22:03:49
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
