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

题目的主要信息：

• n个活动，有各自的区间
• 一个主持人不能在相交的区间工作
• 将相交的区间分成一组，最后组数即是主持人的数量
• 数字为int型的范围，可能会出现负数

举一反三：

学习完本题的思路你可以解决如下题目：

BM89. 合并区间

BM95. 分糖果问题

方法一：排序+遍历比较（推荐使用）

知识点：贪心思想

贪心思想属于动态规划思想中的一种，其基本原理是找出整体当中给的每个局部子结构的最优解，并且最终将所有的这些局部最优解结合起来形成整体上的一个最优解。

思路：

我们利用贪心思想，什么时候需要的主持人最少？那肯定是所有的区间没有重叠，每个区间首和上一个的区间尾都没有相交的情况，我们就可以让同一位主持人不辞辛劳，一直主持了。但是题目肯定不是这种理想的情况，那我们需要对交叉部分，判断需要增加多少位主持人。

具体做法：

• step 1: 利用辅助数组获取单独各个活动开始的时间和结束时间，然后分别开始时间和结束时间进行排序，方便后面判断是否相交。
• step 2: 遍历$nn$个活动，如果某个活动开始的时间大于之前活动结束的时候，当前主持人就够了，活动结束时间往后一个。
• step 3: 若是出现之前活动结束时间晚于当前活动开始时间的，则需要增加主持人。

Java代码实现

import java.util.*;
public class Solution {
    public int minmumNumberOfHost (int n, int[][] startEnd) {
        int[] start = new int[n];
        int[] end = new int[n];
        //分别得到活动起始时间
        for(int i = 0; i < n; i++){
            start[i] = startEnd[i][0];
            end[i] = startEnd[i][1];
        }
        //单独排序
        Arrays.sort(start, 0, start.length);
        Arrays.sort(end, 0, end.length);
        int res = 0;
        int j = 0;
        for(int i = 0; i < n; i++){
            //新开始的节目大于上一轮结束的时间，主持人不变
            if(start[i] >= end[j]) 
                j++;  
            else
                //主持人增加
                res++;  
        }
        return res;
    }
}

C++代码实现

class Solution {
public:
    int minmumNumberOfHost(int n, vector<vector<int> >& startEnd) {
        vector<int> start;
        vector<int> end;
        //分别得到活动起始时间
        for(int i = 0; i < n; i++){
            start.push_back(startEnd[i][0]);
            end.push_back(startEnd[i][1]);
        }
        //分别对开始和结束时间排序
        sort(start.begin(), start.end());
        sort(end.begin(), end.end());
        int res = 0;
        int j = 0;
        for(int i = 0; i < n; i++){
            //新开始的节目大于上一轮结束的时间，主持人不变
            if(start[i] >= end[j]) 
                j++;  
            else
                //主持人增加
                res++;  
        }
        return res;
    }
};

Python实现代码：

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

复杂度分析：

• 时间复杂度：$O(nlo{g}_{2}n)O(nlog\_2n)$，遍历都是$O(n)O(n)$，sort排序为$O(nlo{g}_{2}n)O(nlog\_2n)$
• 空间复杂度：$O(n)O(n)$，辅助空间记录开始时间和结束时间的数组

方法二：重载排序+大顶堆（扩展思路）

知识点：优先队列

优先队列即PriorityQueue，是一种内置的机遇堆排序的容器，分为大顶堆与小顶堆，大顶堆的堆顶为最大元素，其余更小的元素在堆下方，小顶堆与其刚好相反。且因为容器内部的次序基于堆排序，因此每次插入元素时间复杂度都是$O(lo{g}_{2}n)O(log\_2n)$，而每次取出堆顶元素都是直接取出。

具体做法：

• step 1：重载sort函数，将开始时间早的活动放在前面，相同情况下再考虑结束时间较早的。
• step 2：使用小顶堆辅助，其中堆顶是还未结束的将要最快结束的活动的结束时间。
• step 3：首先将int的最小数加入堆中，遍历每一个开始时间，若是堆顶的结束时间小于当前开始时间，可以将其弹出，说明少需要一个主持人。
• step 4：除此之外，每次都需要将当前的结束时间需要加入堆中，代表需要一个主持人，最后遍历完成，堆中还有多少元素，就需要多少主持人。

图示：

Java代码实现

import java.util.*;
public class Solution {
    public int minmumNumberOfHost (int n, int[][] startEnd) {
        int A[] = new int[n];
        int k = 0;
        //按列排序，按开始时间递增排
        Arrays.sort(startEnd, new Comparator<Object>() {
			public int compare(Object o1,Object o2) {
				int[] one = (int[]) o1;
				int[] two = (int[]) o2;
				if(one[0]>two[0]) return 1;
                if(one[0]==two[0]) return 0;
				else return -1;
			}
		});
        //小顶堆
        PriorityQueue<Integer> q = new PriorityQueue<Integer>();
        //可能有负区间
        q.offer(Integer.MIN_VALUE);
        for(int i = 0; i < n; i++){
            //最近的活动结束时间小于当前活动开始时间
            if(q.peek() <= startEnd[i][0])
                q.poll();
            q.offer(startEnd[i][1]);
        }
        //剩余的活动等于主持人数
        return q.size();
    }
}

C++代码实现

class Solution {
public:
    //优先比较开始时间，再比较结束时间
    static bool comp(vector<int>& a, vector<int>& b){ 
        if(a[0] == b[0])
            return a[1] < b[1];
        else
            return a[0] < b[0];
    }
    int minmumNumberOfHost(int n, vector<vector<int> >& startEnd) {
        sort(startEnd.begin(), startEnd.end(), comp);
        //小顶堆
        priority_queue<int, vector<int>, greater<int> > q; 
        //可能有负区间
        q.push(INT_MIN); 
        for(int i = 0; i < n; i++){
            //最近的活动结束时间小于当前活动开始时间
            if(q.top() <= startEnd[i][0])  
               q.pop();
            q.push(startEnd[i][1]);
        }
        //剩余的活动等于主持人数
        return q.size();
    }
};

Python实现代码：

from queue import Queue, PriorityQueue
class Solution:
    #优先比较开始时间，再比较结束时间
    def comp(a:List[int], b: List[int]): 
        if a[0] == b[0]:
            return a[1] - b[1]
        else:
            return a[0] - b[0]
        
    def minmumNumberOfHost(self , n: int, startEnd: List[List[int]]) -> int:
        startEnd.sort(key = functools.cmp_to_key(Solution.comp))
        #小顶堆
        q = PriorityQueue() 
        #可能有负区间
        q.put(-2147483648) 
        for i in range(n):
            temp = q.get()
            #最近的活动结束时间小于当前活动开始时间
            if temp > startEnd[i][0]:  
                q.put(temp)
            q.put(startEnd[i][1])
        #剩余的活动等于主持人数
        return q.qsize()

复杂度分析：

• 时间复杂度：$O(nlo{g}_{2}n)O(nlog\_2n)$，sort排序是$O(nlo{g}_{2}n)O(nlog\_2n)$，一次遍历，循环中维护堆每次$O(lo{g}_{2}n)O(log\_2n)$
• 空间复杂度：$O(n)O(n)$，堆大小最大为$nn$