题解 | #主持人调度（二）#两种思路都写

#include <climits>
#include <functional>
#include <queue>
#include <sys/types.h>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算成功举办活动需要多少名主持人
     * @param n int整型 有n个活动
     * @param startEnd int整型vector<vector<>> startEnd[i][0]用于表示第i个活动的开始时间，startEnd[i][1]表示第i个活动的结束时间
     * @return int整型
     */
    bool compareEvent(vector<int> a,vector<int> b){
        if(a[0]!=b[0])return a[0]<b[0];
        return a[1]<b[1];
    };
    int minmumNumberOfHost(int n, vector<vector<int> >& startEnd) {
        // write code here
        /*策略可以分为，
        1先排序再模拟，用一个队列记录当前正在发生的活动，时间复杂度nlogn，可以当成n^2，空间复杂度O(1)
        2用一个记录着每个时间点变化的数组代表每个时间点的变化情况（差分数组），需要遍历数组两遍，时间复杂度2n+T，空间复杂度O(T)
        总之都写一遍
        */
        
            
        long startTime=INT_MAX,endTime=INT_MIN;

        //统计开始与结束时间点
        for(auto &t : startEnd){
            if(t[0]<startTime)startTime=t[0];
            if(t[1]>endTime)endTime=t[1];
        }
        long timeSpan=endTime-startTime+1;
        int counter=0,maxHost=0;
        if((timeSpan+startEnd.size()<(startEnd.size()*startEnd.size())) && timeSpan<(2<<26)){
            //题目给了256mb=2^(8+10+10)个byte的存储空间，一个int占用4byte，所以数组最长到比2^26略小的位置。鉴于题目如果超出会超出很多，所以这里用2^26判断
            cout<<"选择差分法"<<endl;
            //差分数组法
            cout<<startTime<<' '<<endTime<<' '<<timeSpan<<' '<<INT_MAX<<endl;
            //构建差分数组
            int simulator[timeSpan];
            std::fill(simulator,simulator+timeSpan,0);
            for(auto &t : startEnd){
                ++simulator[t[0]-startTime];
                --simulator[t[1]-startTime];
            }

            //开始扫描
            for(int i=0;i<timeSpan;++i){
                counter+=simulator[i];
                if(maxHost<counter)maxHost=counter;
            }
        }else{
            cout<<"选择模拟法"<<endl;
            sort(startEnd.begin(),startEnd.end(),[](vector<int> a,vector<int> b){
                if(a[0]!=b[0])return a[0]<b[0];
                return a[1]<b[1];
            });

            priority_queue<int,vector<int>,greater<int>> currentPlaying;//只需要记录结束时间

            for(auto &cur : startEnd){

                while(currentPlaying.size() && currentPlaying.top()<=cur[0]){
                    //cout<<currentPlaying.top()<<endl;
                    currentPlaying.pop();
                }
                
                currentPlaying.push(cur[1]);
                if(currentPlaying.size()>maxHost)maxHost=currentPlaying.size();
            }



        }
        return maxHost;

        
    }
};

写完总结其实两种做法的主要思想都是模拟，和贪心/动态规划没啥关系

复习了下空间相关的知识和先序队列