#yyds干货盘点# 面试必刷TOP101:主持人调度(二)

1.简述:

描述

有 n 个活动即将举办,每个活动都有开始时间与活动的结束时间,第 i 个活动的开始时间是 starti ,第 i 个活动的结束时间是 endi ,举办某个活动就需要为该活动准备一个活动主持人。一位活动主持人在同一时间只能参与一个活动。并且活动主持人需要全程参与活动,换句话说,一个主持人参与了第 i 个活动,那么该主持人在 (starti,endi) 这个时间段不能参与其他任何活动。求为了成功举办这 n 个活动,最少需要多少名主持人。数据范围: #yyds干货盘点# 面试必刷TOP101:主持人调度(二) , #yyds干货盘点# 面试必刷TOP101:主持人调度(二)

复杂度要求:时间复杂度 #yyds干货盘点# 面试必刷TOP101:主持人调度(二) ,空间复杂度 #yyds干货盘点# 面试必刷TOP101:主持人调度(二)

示例1

输入:

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

返回值:

1

说明:

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

示例2

输入:

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

返回值:

2

说明:

需要两个主持人才能成功举办这两个活动
import java.util.*;
public class Solution {
public int minmumNumberOfHost (int n, int[][] startEnd) {
int[] start = new int[n];
int[] end = new int[n];
//分别得到活动起始时间
for(int i = 0; i < n; i++){
start[i] = startEnd[i][0];
end[i] = startEnd[i][1];
}
//单独排序
Arrays.sort(start, 0, start.length);
Arrays.sort(end, 0, end.length);
int res = 0;
int j = 0;
for(int i = 0; i < n; i++){
//新开始的节目大于上一轮结束的时间,主持人不变
if(start[i] >= end[j])
j++;
else
//主持人增加
res++;
}
return res;
}
}
发表评论

相关文章