主持人调度（二）

C++ 解法, 执行用时: 32ms, 内存消耗: 5960KB, 提交时间: 2021-07-26

static const auto io_sync_off = []()
{
    // turn off sync
    std::ios::sync_with_stdio(false);
    // untie in/out streams
    std::cin.tie(nullptr);
    return nullptr;
}();
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) {
        sort(startEnd.begin(), startEnd.end(), [](auto &x, auto &y) {
            if(x[0] == y[0]) return x[1] < y[1];
            return x[0] < y[0];
        });
        priority_queue <int, vector <int>, greater<int> > ss;
        for(auto &c : startEnd) {
            if(!ss.empty() && c[0] >= ss.top()) ss.pop();
            ss.push(c[1]);
        }
        return ss.size();
    }
};

C++ 解法, 执行用时: 42ms, 内存消耗: 5896KB, 提交时间: 2021-07-11

static const auto io_sync_off = []()
{
    // turn off sync
    std::ios::sync_with_stdio(false);
    // untie in/out streams
    std::cin.tie(nullptr);
    return nullptr;
}();
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) {
        // write code here
        if(n < 2) return n;
        
        sort(startEnd.begin(), startEnd.end());
        priority_queue<int, vector<int>, greater<int>> i_prio_queue;
        i_prio_queue.push( startEnd[0][1] );   int len = startEnd.size();
        for(int i=1; i<len; i++){
            if(startEnd[i][0] >= i_prio_queue.top())
                i_prio_queue.pop();
            i_prio_queue.push( startEnd[i][1] );
        }
        return i_prio_queue.size();
    }
};

C++ 解法, 执行用时: 43ms, 内存消耗: 5916KB, 提交时间: 2021-07-28

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) {
        // write code here
        if(0 == n)
            return 0;
        vector<int>start(n);
        vector<int>end(n);
        for(int i = 0; i < n; i++)
        {
            start[i] = startEnd[i][0];
            end[i] = startEnd[i][1];
        }
        sort(start.begin(), start.end());
        sort(end.begin(), end.end());
        int res = 0;
        for(int s = 0, e = 0; s < n; s++)
        {
            if(start[s] < end[e])
                res++;
            else 
                e++;
        }
        return res;
    }
};

C++ 解法, 执行用时: 45ms, 内存消耗: 6232KB, 提交时间: 2021-07-23

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> starts(n), ends(n);
        for(int i=0; i<n; ++i)
        {
            starts[i] = startEnd[i][0];
            ends[i] = startEnd[i][1];
        }
        sort(starts.begin(), starts.end());
        sort(ends.begin(), ends.end());
        int ans = 0;
        for(int s=0, e=0; s<n; ++s)
        {
            if(starts[s] < ends[e])
            {
                ++ ans;
            }
            else
            {
                ++ e;
            }
        }
        return ans;
    }
};

C++ 解法, 执行用时: 45ms, 内存消耗: 7220KB, 提交时间: 2021-07-29

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) {
        // write code here
        int MaxCount = 0;
        vector<int> start;
        vector<int> end;
        for(int i = 0 ; i < n; i++)
        {
            if(startEnd[i].size() == 2)
            {
                start.push_back(startEnd[i][0]);
                end.push_back(startEnd[i][1]);
            }
        }
        sort(start.begin(), start.end());
        sort(end.begin(),end.end());
        int index = 0;
        int count =0;
        int i = 0;
        int j = 0;
        for(auto time : start)
        {
            while(i < n && start[i] <= time)
            {
                i++;
                count++;
            }
            while(j < n && end[j] <= time)
            {
                j++;
                count--;
            }
            if(MaxCount < count)
                MaxCount = count;
        }
        return MaxCount;
    }
};

详情