一位活动主持人在同一时间只能参与一个活动。并且活动主持人需要全程参与活动，换句话说，一个主持人参与了第 i 个活动，那么该主持人在 (starti,endi) 这个时间段不能参与其他任何活动。求为了成功举办这 n 个活动，最少需要多少名主持人。
数据范围:
复杂度要求：时间复杂度 )
，空间复杂度 )
[编程题]主持人调度（二）
- 热度指数：60618 时间限制：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
回复(0)
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)
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
回复(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)
这道题有个有趣的一点，值得注意：
相同索引（i）时, startArr[i] <= endArr[i]:
假如对最开始的二维数组排序，如果按照它元素的的第一个索引（start[i][0]）的值排序，那么start[i][1] 则有可能小于 start[i+1][1], 由于 start[i+1][1] 一定大于 start[i+1][0], 而start [i+1][0] 一定大于等于 start[i][0]， 因此，相同索引的 startArr[i] 一定小于 endArr[i]
这道题使用了贪心算法的思想，最开始的时候就使用最小结束元素，使得交集的区间最小，如果不再产生交集时再逐步放大结束元素，使得可以继续产生交集，直到结束元素用尽，则直接获得最大交集数，但这种思想仅适合解决有穷的离散数学问题，对于无穷个元素的连续数学问题，则贪心算法不满足：
public int minmumNumberOfHost(int n, int[][] startEnd) {
// write code here
if (startEnd.length <= 1)
return startEnd.length;
int len = startEnd.length;
int[] startArr = new int[len];
int[] endArr = new int[len];
for (int i = 0; i < len; i++) {
startArr[i] = startEnd[i][0];
endArr[i] = startEnd[i][1];
}
Arrays.sort(startArr);
Arrays.sort(endArr);
int least = 1;
int endIndex = 0;
for (int startIndex = 1; startIndex < len; startIndex++) {
// 断言没问题，勿质疑
assert startArr[startIndex] <= endArr[startIndex];
if(startArr[startIndex] >= endArr[endIndex])
endIndex ++;
else
least ++;
}
return least;
}
编辑于 2024-04-15 14:45:27
回复(0)
#include <algorithm>
#include <vector>
class Solution {
public:
int minmumNumberOfHost(int n, vector<vector<int> >& startEnd) {
vector<int>sta;
vector<int>end;
if(startEnd.size()==0){
return 0;
}
for(int i=0;i<startEnd.size();i++){
sta.push_back(startEnd[i][0]);
end.push_back(startEnd[i][1]);
}
sort(sta.begin(), sta.end());
sort(end.begin(),end.end());
int ans=1,sl=0;
for(int i=1;i<sta.size();i++){
while (sta[i]<end[sl]&&i<sta.size()){
ans++;
i++;
}
sl++;
}
return ans;
}
};
编辑于 2024-04-07 13:48:40
回复(0)
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
int partition(int** arr, int left, int right, int part) {
int pivot = arr[right][part];
int i = left - 1;
for (int j = left; j < right; j++) {
if (arr[j][part] < pivot) {
i++;
swap(&arr[i][part], &arr[j][part]);
}
}
swap(&arr[i + 1][part], &arr[right][part]);
return i + 1;
}
void quicksort(int** arr, int left, int right, int part) {
if (left < right) {
int pivot = partition(arr, left, right, part);
quicksort(arr, left, pivot - 1, part);
quicksort(arr, pivot + 1, right, part);
}
}
int minmumNumberOfHost(int n, int** startEnd, int startEndRowLen,
int* startEndColLen ) {
int i, j;
for(i = 0; i < n/2; i++) {
if(memcmp(startEnd[2*i], startEnd[2*i+1], 2*sizeof(int))!=0) {
quicksort(startEnd, 0, n-1, 0);
quicksort(startEnd, 0, n-1, 1);
break;
}
}
for (i = 1, j = 0; i < n; i++) {
if (startEnd[i][0] >= startEnd[j][1])
j++;
}
return i-j;
}
编辑于 2024-03-26 23:03:41
回复(0)
问题信息
难度：
69条回答
779收藏
5045浏览
通过挑战的用户
查看代码-
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群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
