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

class Solution {
    struct cmp{
        bool operator()(const pair<int,int>& a, const pair<int,int>& b){
            return a.first>b.first;
        }
    };
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) {
        // write code here
        sort(startEnd.begin(),startEnd.end(),[](const vector<int>& a, const vector<int>& b){
            return a[0]==b[0] ? a[1]<b[1] : a[0]<b[0];
        });
        vector<vector<int>> vec(1,vector<int>{startEnd[0][1]-startEnd[0][0],startEnd[0][1]});

        //使用优先队列，默认是从小到大排序的大顶堆（从队尾取元素），改为从大到小排序，同cmp
        priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pque;
        pque.push(pair<int,int>{vec[0][1],0});
        for(int i=1; i<n; i++){
            vector<int> temp = startEnd[i];
            bool flag = false;
            auto iter = pque.top();
            //cout<<iter.first<<":"<<iter.second<<endl;
            if(iter.first<=temp[0]){
                int j = iter.second;
                vec[j][0]+=temp[1]-temp[0];
                vec[j][1] = temp[1];
                flag = true;
                pque.pop();
                pque.push(pair<int,int>{temp[1],j});
            }
            if(flag) continue;
            vec.push_back(vector<int>{temp[1]-temp[0],temp[1]});
            pque.push(pair<int,int>{temp[1],(int)vec.size()-1});
        }
        while(pque.size()){
            cout<<pque.top().first<<':'<<pque.top().second<<endl;
            pque.pop();
        }
        //for(auto nn1:vec){for(auto nn2:nn1)cout<<nn2<<' ';cout<<endl;}

        return vec.size();
    }
};