题解 | #主持人调度#

思路：

题目的主要信息：

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

方法一：排序+遍历比较
具体做法：
利用辅助数组单独各个活动开始的时间和结束时间，然后分别进行排序。遍历个活动，如果某个活动开始的时间大于之前活动结束的时候，当前主持人就够了，活动结束时间往后一位，若是出现之前活动结束时间晚于当前活动开始时间的，需要增加主持人。

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;
    }
};

复杂度分析：

• 时间复杂度：，遍历都是，sort排序为
• 空间复杂度：，辅助空间记录开始时间和结束时间的数组

方法二：重载sort+大顶堆
具体做法：
重载sort函数，优先排开始时间小的，相同情况下再考虑结束时间较小的。
使用小顶堆辅助，其中堆顶是还未结束的将要最快结束的活动的结束时间。首先将int的最小数加入堆中，遍历每一个开始时间，若是堆顶的结束时间小于当前开始时间，可以将其弹出，说明少需要一个主持人；除此之外，每次都需要将当前的结束时间需要加入堆中，代表需要一个主持人，最后遍历完成，堆中还有多少元素，就需要多少主持人。

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();
    }
};

复杂度分析：

• 时间复杂度：，sort排序是，一次遍历，循环中维护堆每次
• 空间复杂度：，堆大小最大为n