题解｜NC147主持人调度

主持人调度

描述
有n个活动即将举办，每个活动都有活动的开始时间与活动的结束时间，第i个活动的开始时间是,第i个活动的结束时间是,举办某个活动就需要为该活动准备一个活动主持人。一位活动主持人在同一时间只能参与一个活动。并且活动主持人需要全程参与活动，换句话说，活动主持人参与了第i个活动，那么该主持人在,这个时间段不能参与其他任何活动。求为了成功举办这n个活动，最少需要多少名主持人。

这道题的核心思路是在于考察同一时刻最多有多少场活动同时进行。

解法1: 遍历时刻
先根据所有活动的起止时间，获得最先开始的时间和最后开始的时间。
因为所有的起止时间都是整数，所以我们可以按整数进行遍历。并对每一时刻统计，这一时刻有多少活动正在进行。
时间复杂度：，空间复杂度

解法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) {
        std::sort(startEnd.begin(), startEnd.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[0] < b[0];
        });
        std::priority_queue<int, std::vector<int>, std::greater<int>> heap;
        int result = 0;
        for (auto &v : startEnd) {
            while (!heap.empty() && heap.top() <= v[0]) heap.pop();
            heap.push(v[1]);
            result = std::max(result, static_cast<int>(heap.size()));
        }
        return result;
    }
};

解法3: 按时刻统计活动数量
由题可知，活动数量只会在活动开始或者活动结束的时候变化。
所以我们只需要记录这些时刻活动数量的变化值，就可以通过累加得到活动数量的变化，进而求得活动数量的最大值。
时间复杂度：，空间复杂度

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) {
        std::map<int, int> counter;
        for (auto &v : startEnd) {
            counter[v[0]]++;
            counter[v[1]]--;
        }
        int sum = 0;
        int result = 0;
        for (auto &v : counter) {
            sum += v.second;
            result = std::max(result, sum);
        }
        return result;
    }
};