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

主持人调度（二）,官方题解1精简版（7行）与超详细思路梳理

官方题解1挺巧妙的，试着梳理一下思路。求最小的主持人数，等价于求最大区间重叠数。然而区间在哪里具有最大重叠我们是不知道的，如果一个一个遍历去找时间得O(n^2)，如何O(nlogn)实现呢。

我们的目标是找最大重叠，只要起点终点不混，不同区间的起点交换或者终点交换并不会影响最大重叠。所以，对起点和终点分别进行排序，在排序后的起点终点构成新的区间上找最大重叠。由于起点终点都是排好序的，在每个新的区间内出现的其他区间的起点数+1就是该区间内的最大重叠数。

也就是说，我们只需要遍历每个新区间，然后依次统计每个区间内的最大重叠数，然后维护一个全局最大重叠数res就可以得到结果了，不过这样也是O(n^2)，因为在统计第i个区间的最大重叠数时，需要把i-1时遍历其他区间的起点的指针j退回到i+1然后重新遍历，这样的回退导致了O(n^2)。

官方题解1给的就是不回退的办法，开始时，如果没有遇到重叠start[j] >= end[i]，则起点终点同步往后移动，如果遇到重叠start[j] < end[i]，此时最大重叠数为N(重叠包含自身)，则终点滞后起点N-1，那么对于end[i+1]来说，相当于直接跳过了N个起点，如果[start[i+1],end[i+1]]内起点数n小于等于N，那么忽略了N个起点后，start[j+1]必然大于end[i+1]，相当于直接跳过该重叠区间。只有当[start[i+1],end[i+1]]内起点数n大于N时，忽略了N个起点后n-N个起点满足start<end[i+1]，此时最大重叠数为n，此后终点将滞后起点n-1.....，如此往复，到最后，起点滞后终点的长度+1就是最大最大重叠数。

class Solution:
    def minmumNumberOfHost(self , n: int, startEnd: List[List[int]]) -> int:
        start = sorted([v[0] for v in startEnd])
        end = sorted([v[1] for v in startEnd])
        i = j = 0
        for j in range(len(start)):
            if start[j] >= end[i]:
                i += 1
        return j - i + 1