主持人如何进行调度，你学会了吗？

主持人调度

问题描述

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

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

示例：

输入：2，[[1,2],[2,3]]

返回值：1

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

分析问题

因为一名主持人在同一时间只能参加一个活动，即如果时间上相邻的两个活动，如果第一个活动的结束时间小于第二个活动的开始时间，那么我们就用一名主持人就能主持这两个活动；如果第一个活动的结束时间大于第二个活动的开始时间，那么就需要二个主持人来主持这个两个活动。

我们可以使用优先级队列来求解，具体来说。

1. 首先对活动进行排序处理，排序规则如下。
   • 按照开始时间从小到大排序。
   • 如果开始时间相同，则按结束时间从小到大排序。
2. 建立一个优先级队列（小顶推，最小的元素在堆顶），队列中只存储活动的结束时间。
3. 遍历已经排好序的活动。
   • 如果当前活动的开始时间小于队首的结束时间，说明主持人没空闲。
   • 如果当前活动的开始时间大于队首的结束时间，说明可以空闲一个主持人，我们将队首元素出队。
   • 我们将该活动的结束时间入队。
4. 最终优先级队列的大小即为需要的主持人的数。

下面我们来看一下代码实现。

import heapq
import functools
class Solution:
    def minmumNumberOfHost(self,n,startEnd):
        # write code here
        # 首先对活动进行排序
        def cmp(a, b):
            if a[0] == b[0]:
                return a[1] - b[1]
            else:
                return a[0] - b[0]
        startEnd = sorted(startEnd, key=functools.cmp_to_key(cmp))
        #第一个元素入队
        queue=[startEnd[0][1]]
        heapq.heapify(queue)
        for a in startEnd[1:]:
            #如果当前的开始时间大于队首的结束时间，说明可以空闲一个，队首出队
            if queue[0] <= a[0]:
                heapq.heappop(queue)
            #将当前活动的结束时间入队    
            heapq.heappush(queue, a[1])
            
        return len(queue)

该算法的时间复杂度是O(nlogn)。因为排序的时间复杂度是O(nlogn)，优先级队列queue是一个小顶堆，插入和删除的时间需要O(logn)，总共需要操作n次，所以该算法的时间复杂度是O(nlogn)。在最坏情况下，需要额外大小为n的堆存储结束时间，所以空间复杂度为O(n)。

这道题我们还可以使用贪心法来求解。

1. 首先，我们建立两个数组start和end，分别来存储活动的开始时间和结束时间。
2. 然后，我们对两个数组从小到大进行排序。
3. 接下来，我们遍历数组start，然后去判断当前活动的开始时间是否大于等于最小的结束时间。如果是，则说明当前主持人可以搞定（对应当前最小的结束时间的那个活动），并将end数组下标后移一位；如果否，则需要新增加一个主持人。

下面我们来看一下代码的实现。

class Solution:
    def minmumNumberOfHost(self,n,startEnd):
        # write code here
        # 初始化两个数组，分别保存活动的开始时间和结束时间
        if n==0:
            return 0
        start=[]
        end=[]
        for i in range(n):
            start.append(startEnd[i][0])
            end.append(startEnd[i][1])
        start = sorted(start)
        end = sorted(end)
        index=0
        res=0
        for i in range(n):
            #如果开始时间大于等于最小的结束时间，
            #说明该主持人可以搞定,所以index+1
            if start[i] >= end[index]:
                index=index+1
            else:
                #否则新增一个主持人
                res=res+1
        return res

该算法的时间复杂度是O(nlogn)，因为需要进行排序，排序的时间复杂度是O(nlogn)，所以该算法的时间复杂度是O(nlogn)。

该算法的空间复杂度是O(n)，需要额外大小为n的start和end数组，所以该算法的空间复杂度是O(n)。