描述
有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; } };