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

标签：贪心

本题的解题规律没有整明白，代码完全拷至： https://blog.nowcoder.net/n/147d14b917ba4eaca2c951628aaa5a30

解题思路：

step 1: 利用辅助数组获取单独各个活动开始的时间和结束时间，然后分别开始时间和结束时间进行排序，方便后面判断是否相交。

step 2: 遍历n个活动，如果某个活动开始的时间大于之前活动结束的时候，当前主持人就够了，活动结束时间往后一个。

step 3: 若是出现之前活动结束时间晚于当前活动开始时间的，则需要增加主持人。

class Solution:
    def minmumNumberOfHost(self , n: int, startEnd: List[List[int]]) -> int:
        start = list()
        end =list()
        #分别得到活动起始时间
        for i in range(n):
            start.append(startEnd[i][0])
            end.append(startEnd[i][1])
        #分别对开始和结束时间排序
        start.sort()
        end.sort()
        res = 0
        j = 0
        for i in range(n):
            #新开始的节目大于上一轮结束的时间，主持人不变
            if start[i] >= end[j]: 
                j += 1
            else:
                #主持人增加
                res += 1  
        return res

道理都明白，思路差不多，但自己实现的代码运行超时了……

class Solution:
    def minmumNumberOfHost(self , n: int, startEnd: List[List[int]]) -> int:
        temp = sorted(startEnd, key=lambda x: (x[0], x[1]))
        # 用于保存每个主持人的活动时间区间
        nums = [temp[0]]
        # 以主持人为单位，遍历所有活动，判断可以给哪个主持人安排
        for i in range(1, len(temp)):
            for j in range(len(nums)):
                if temp[i][0] >= nums[j][1]:
                    nums[j][1] = temp[i][1]
                    break
                else:
                    if j == len(nums) - 1:
                        nums.append(temp[i])
        return len(nums)