牛客网：主持人调度

 这里有两种方法做，贪心和排序：

目录

1.贪心

2.排序

---

1.贪心

这里其实很容易想到贪心算法，但是要怎么处理呢？很容易想到排序，这里我们对开始时间和结束时间排序。然后我们维护一个东西：

1.当前活动的开始时间

2.上一个最快结束的结束时间或者上一个最快已经结束的时间

这里第二个有点不好理解，我们来具体走一遍处理思路：

设有开始时间start[i]和结束时间end[j]，这里两个序列是我们对开始时间和结束时间排序的结果

1.如果start[i]>=end[j]，说明上一个活动刚好结束，说明我们可以从上一个活动直接抽出一个主持人，那么我们根本不需要再多加一个主持人，这个时候就直接结束上一个活动看下一个，即j++

2.否则，说明需要增加主持人的数量

代码如下所示：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算成功举办活动需要多少名主持人
     * @param n int整型 有n个活动
     * @param startEnd int整型vector<vector<>> startEnd[i][0]用于表示第i个活动的开始时间，startEnd[i][1]表示第i个活动的结束时间
     * @return int整型
     */    
    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;
    }
};

这里的时间复杂度是O(nlogn) 

2.排序

用堆排序，本质上还是用了之前的思想，即当前的活动向之前的未结束活动借人，如果借的到，那么人数就不变，如果借不到，那么人数要加一。

具体转化为操作如下所示：

首先对数组排序，按照start时间优先end的从小到大排序

然后我们维护一个最小堆，这个堆维护结束时间，堆顶的含义是一个活动的最早结束时间：

1.如果当前活动时间开始时间大于等于堆顶，那么说明可以向前面借一个主持人，直接将栈顶pop然后再push当前活动的结束时间

2.否则，直接push

这样，最后留下来的节点个数就是主持人的最小数量

实现上由于可能出现负数，所以一开始要pushINT_MIN，来保证增加第一个主持人

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算成功举办活动需要多少名主持人
     * @param n int整型 有n个活动
     * @param startEnd int整型vector<vector<>> startEnd[i][0]用于表示第i个活动的开始时间，startEnd[i][1]表示第i个活动的结束时间
     * @return int整型
     */ 
    bool cmp(vector<int> &a, vector<int> &b){
        if(a[0]==a[0]){
            return a[1]<b[1];
        }
        return a[0]<b[0];
    }
    int minmumNumberOfHost(int n, vector<vector<int> >& startEnd) {
        sort(startEnd.begin(), startEnd.end());
        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();
    }
};