首页 > 试题广场 >

主持人调度（二）

[编程题]主持人调度（二）

热度指数：71271 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

有 n 个活动即将举办，每个活动都有开始时间与活动的结束时间，第 i 个活动的开始时间是 start_i ,第 i 个活动的结束时间是 end_i ,举办某个活动就需要为该活动准备一个活动主持人。

一位活动主持人在同一时间只能参与一个活动。并且活动主持人需要全程参与活动，换句话说，一个主持人参与了第 i 个活动，那么该主持人在 (start_i,end_i) 这个时间段不能参与其他任何活动。求为了成功举办这 n 个活动，最少需要多少名主持人。

数据范围: $1 \le n \le 10^5$ ， $-2^{32} \le start_i\le end_i \le 2^{31}-1$

复杂度要求：时间复杂度 $O(n \log n)$ ，空间复杂度 $O(n)$

示例1

输入

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

输出

说明

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

示例2

输入

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

输出

说明

需要两个主持人才能成功举办这两个活动

备注:


在int范围内

算法知识视频讲解

Python 3

牛客847442772号

这题目有歧义吧同时开始同时结束也算一个活动吧也要分配一个人去主持吧难道1,[123,123]这个用例输出0？

发表于 2024-10-31 20:58:56 回复(0)

Python 3

HackerLzh

关键词：排序，小顶堆，模拟

import heapq
class Solution:
    def minmumNumberOfHost(self , n: int, startEnd: List[List[int]]) -> int:
        # write code here
        hosts = 0
        rest = 0
        past = 0
        ending_nums = []
        sorted_list = sorted(startEnd, key=lambda x: (x[0], x[1]))
        for a in sorted_list:
            # finshed possible events
            while len(ending_nums) > 0:
                if ending_nums[0] in range(past, a[0] + 1):
                    heapq.heappop(ending_nums)
                    rest += 1
                else:
                    break
            past = a[0]
            # assign event
            if rest > 0:
                rest -= 1
            else:
                hosts += 1
            heapq.heappush(ending_nums, a[1])
        return hosts

发表于 2024-07-08 18:15:12 回复(0)

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

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号

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

优先级队列

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

开始时间相等的，结束时间从小到大
开始时间不相等的，开始时间从小到大
直接使用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

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)

提交观点

问题信息

贪心

难度：

8条回答 912收藏 5836浏览

通过挑战的用户

查看代码

牛客63450...

2023-03-14 12:15:24
牛客3340351号

2023-03-13 16:58:17
😭呜呜

2023-02-26 11:03:29
牛客58768...

2023-02-23 17:06:37
emo的大熊猫...

2023-02-19 22:03:49

主持人调度（二）

输入

输出

说明

输入

输出

说明

备注:

优先级队列

问题信息

热门推荐

通过挑战的用户

相关试题