首页 > 试题广场 >

主持人调度（二）

[编程题]主持人调度（二）
  • 热度指数：62707 时间限制：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范围内
算法知识视频讲解
添加回答
Python 3
铁离子头像 铁离子 
import heapq
class Solution:
    def minmumNumberOfHost(self , n: int, startEnd: List[List[int]]) -> int:
        # write code here
        startEnd.sort(key=lambda x:(x[0],x[1]))
        heap = []
        res = 0
        for s,e in startEnd:
            while len(heap) and heap[0]<=s:
                heapq.heappop(heap)
            heapq.heappush(heap,e)
            res = max(res,len(heap))
        return res

发表于 2022-07-12 12:10:17 回复(0)
Python 3
宫城良田z头像 宫城良田z 
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)
Python 3
牛客760622808号头像 牛客760622808号
python 贪心 
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 计算成功举办活动需要多少名主持人
# @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 = [] , []
        for s,e in startEnd:
            start.append(s)
            end.append(e)
        start.sort()
        end.sort()
        
        res = 0
        i , j = 0, 0
        while i < n:
            if start[i] >= end[j]:
                j += 1
            else:
                res += 1
            i += 1
        return res


发表于 2021-11-07 09:31:43 回复(0)
Python 3
JennyWu头像 JennyWu

优先级队列

首先：要对活动进行排序：

  • 开始时间相等的，结束时间从小到大
  • 开始时间不相等的，开始时间从小到大
  • 直接使用Python sort函数对二维数组排序，默认先按照x[0]排，x[0]相同时，按照x[1]排，以此类推

其次：建立一个优先级队列：默认升序，同时处理活动

  • 只提供结束时间，如果当前的开始时间小于队首的结束时间，说明没空闲
  • 如果当前的开始时间大于队首的结束时间，说明可以空闲一个，队首出队
  • 可直接使用Python的heapq，也可使用二分法构建优先队列
最后返回队列长度，具体如下： 
def insertItem(hq, item):
    if not hq:
        hq.append(item)
        return
    left, right = 0, len(hq) - 1
    index = len(hq) + 1
    
    while left <= right:
        mid = left + (right - left) // 2
        if hq[mid] == item:
            index = mid
            break
        elif hq[mid] > item:
            right = mid - 1
        else:
            left = mid + 1
    if index != len(hq) + 1:
        hq.insert(index, item)
    else:
        hq.insert(left, item)
    
class Solution:
    def minmumNumberOfHost(self , n , startEnd ):
        # write code here
        startEnd.sort()
        hq = [startEnd[0][1]]
        
        for i in range(1, len(startEnd)):
            if startEnd[i][0] >= hq[0]:
                hq.pop(0)
            insertItem(hq, startEnd[i][1])
        return len(hq)



发表于 2021-08-14 18:31:37 回复(0)
Python 3
HHHChen77头像 HHHChen77
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)
提交观点

问题信息

贪心
难度：
6条回答 5133浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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