请选择 进入手机版 | 继续访问电脑版
 找回密码
 立即注册

快捷登录

手机动态码快速登录

手机号快速注册登录

2022-9-14 14:50:39 · 主持

牛客网算法BM96 主持人调度(二)

描述
有 n 个活动即将举办,每个活动都有开始时间与活动的结束时间,第 i 个活动的开始时间是 starti ,第 i 个活动的结束时间是 endi ,举办某个活动就需要为该活动准备一个活动主持人。
一位活动主持人在同一时间只能参与一个活动。并且活动主持人需要全程参与活动,换句话说,一个主持人参与了第 i 个活动,那么该主持人在 (starti,endi) 这个时间段不能参与其他任何活动。求为了成功举办这 n 个活动,最少需要多少名主持人。
数据范围: 1≤n≤105, −232 ≤starti,endi ≤231 −1
复杂度要求:时间复杂度O(nlogn) ,空间复杂度 O(n)
示例1
输入:2,[[1,2],[2,3]]
返回值:1
说明:只需要一个主持人就能成功举办这两个活动
示例2
输入:2,[[1,3],[2,4]]
返回值:2
说明:需要两个主持人才能成功举办这两个活动
备注:
1≤n≤105
start_i,end_istart
starti,endi在int范围内
本题稍微有点难度,其在牛客网上的链接如下,打开该链接,选择BM96即可访问该题星系信息
https://www.nowcoder.com/link/pc_zh_sf98
在解答本题时,关键在于解题思路,通常只要有思路,代码就好编写了,下面我简单介绍下牛客网上提供的解题思路
1.遍历
先根据所有活动的起止时间,获得最先开始的时间和最后开始的时间。
因为所有的起止时间都是整数,所以我们可以按整数进行遍历。并对每一时刻统计,这一时刻有多少活动正在进行。
时间复杂度:O(232n),空间复杂度O(1)
2.通过堆模拟活动的开始和结束
使用堆保存每个活动的结束时间,并在有新活动开始时,把已经结束的活动从堆中删除出去,再将当前活动的结束时间插入堆。
此时堆的大小即为同时存在的活动数量。
通过将所有任务按时间顺序经上述处理,当堆大小最大时,即为活动最多的时刻。
时间复杂度O(nlogn) ,空间复杂度 O(n)
3.按时刻统计活动数量
由题可知,活动数量只会在活动开始或者活动结束的时候变化。
所以我们只需要记录这些时刻活动数量的变化值,就可以通过累加得到活动数量的变化,进而求得活动数量的最大值。
时间复杂度O(nlogn) ,空间复杂度 O(n)


下图是截取的牛客网上提供的代码,供大家参考,实际上,牛客网上还提供了其他思路,且提供了对应代码,感兴趣的可以登录我上面提供的链接查看


全程白嫖传送门:https://www.nowcoder.com/link/pc_zh_sf98
Ps:知乎不支持直接跳转,大家可以直接复制链接到浏览器打开~

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?立即注册 手机动态码快速登录

x

举报

全部评论 0

热门推荐
您需要登录后才可以回帖 立即登录 手机动态码快速登录
说说你的想法......
0
1
0
返回顶部