题解 | #主持人调度（二）#

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 计算成功举办活动需要多少名主持人
# @param n int整型 有n个活动
# @param startEnd int整型二维数组 startEnd[i][0]用于表示第i个活动的开始时间，startEnd[i][1]表示第i个活动的结束时间
# @return int整型
# 思想有点类似于区间合并的感觉奥
# 1.首先按照各个活动的起始时间排序
# 2.使用堆结构存储各个主持人的最后结束时间，因为最小根堆
class Solution:
    def minmumNumberOfHost(self , n: int, startEnd: List[List[int]]) -> int:
        # write code here
        import heapq
        sort_l = sorted(startEnd, key=lambda x:x[0])
        end_l = [sort_l[0][1]] # 小根堆，存所有主持人结束主持的时间
        heapq.heapify(end_l)
        res = 1 # 最开始，第一个活动肯定需要一个主持人
        for item in sort_l[1:]: # 从第二个活动开始遍历
            if item[0] < end_l[0]: # 如果当前活动的起始时间，早于最早结束活动的主持的时间，那么需要再加一个主持人
                res += 1
                heapq.heappush(end_l, item[1]) # 并把新主持人的结束活动时间放进小根堆
            else: # 如果当前活动的起始时间，在最早结束活动的主持人的时间之后，那就安排给这个主持人即可，不用再加
                heapq.heapreplace(end_l, item[1]) # 修改这个主持人的最后结束时间
        return res