主持人调度（一）_牛客题霸_牛客网

有 n 个活动即将举办，每个活动都有开始时间与活动的结束时间，第 i 个活动的开始时间是 starti ,第 i 个活动的结束时间是 endi ,举办某个活动就需要为该活动准备一个活动主持人。

一位活动主持人在同一时间只能参与一个活动。并且活动主持人需要全程参与活动，换句话说，一个主持人参与了第 i 个活动，那么该主持人在 (starti,endi) 这个时间段不能参与其他任何活动。请问一个只有一个主持人能否举办全部活动。

数据范围: 1≤n≤1051≤n≤105 ， 0≤starti,endi≤1090≤starti,endi≤109

        // sort(schedule.begin(), schedule.end(), less()); greater()
        // sort(schedule.begin(), schedule.end());
        // sort(schedule.begin(), schedule.end(), Com());

        回忆一下升序

实现很简单，首先进行一个按照开始时间由前到后排序（使用仿函数排序现在已经司空见惯了），然后前后逐个遍历，如果前一个活动的结束时间晚于当前活动的开始时间，一个主持人无法完成。

class Com
{public:bool operator()(const vector<int>& left, const vector<int>& right){return left[0]<right[0];}
};class Solution {
public:bool hostschedule(vector<vector<int> >& schedule) {// write code heresort(schedule.begin(), schedule.end(), Com());for(int i = 1; i < schedule.size(); i++){if(schedule[i-1][1] > schedule[i][0])return false;}return true;}
};

主持人调度（二）_牛客题霸_牛客网

有 n 个活动即将举办，每个活动都有开始时间与活动的结束时间，第 i 个活动的开始时间是 starti ,第 i 个活动的结束时间是 endi ,举办某个活动就需要为该活动准备一个活动主持人。

一位活动主持人在同一时间只能参与一个活动。并且活动主持人需要全程参与活动，换句话说，一个主持人参与了第 i 个活动，那么该主持人在 (starti,endi) 这个时间段不能参与其他任何活动。求为了成功举办这 n 个活动，最少需要多少名主持人。

数据范围: 1≤n≤1051≤n≤105 ， −232≤starti≤endi≤231−1−232≤starti≤endi≤231−1

复杂度要求：时间复杂度 O(nlog⁡n)O(nlogn) ，空间复杂度 O(n)O(n)

【解法一】思维

1、首先肯定是要进行排序，按照开始时间先后顺序进行排序，当开始时间相同情况下就根据结束时间进行排序。

2、初始化一个bool类型的数组v，进行判断当前元素是否已经分配给了一个主持人。

3、开始给第一个主持人分配活动，首先在bool类型数组v中从前往后找没有被安排的活动，决定给该主持人分配，那么该活动对于的v数组就赋值为True，从后面的活动中找到下一个时间不冲突的活动给该主持人安排上，直到所有的活动遍历完

4、这时候判断是否所有的活动都被安排了，如果还有活动没有被安排，那就在来一个主持人，重新开始3步骤。

这种是可以，就是东西有点多了，遇到疯狂的主持人就会超时。所以要进行优化。

class Com
{
public:bool operator()(const vector<int>& left, const vector<int>& right){if(left[0] == right[0])return left[1]<right[1];elsereturn left[0]<right[0];}
};class Solution {
public:int minmumNumberOfHost(int n, vector<vector<int> >& startEnd) {// write code hereif(n==1)return 1;vector<bool> v(n, false);sort(startEnd.begin(), startEnd.end(), Com());int person = 1;while(true){int pos = 0;for(int i = 0; i < n; i++){if(v[i] == false){pos = i;v[pos] = true;break;}}if(pos == n-1)break;for(int i = pos+1; i < n; i++){if(v[i]==false && startEnd[pos][1] <= startEnd[i][0]){pos = i;v[i] = true;}}if(find(v.begin(), v.end(), false) != v.end())person++;elsebreak;}return person;}
};

【优化】优先队列小根堆

        priority_queue<int, vector<int>, greater<int>> q;

q.push(INT_MIN);        // 防止负数

for(int i = 0; i < n; i++)

{

if(q.top()<=startEnd[i][0])        // 如果最小结束时间小于等于当前任务开始时间

q.pop();                                 // 就可以少使用一个主持人

q.push(startEnd[i][1]);            // 每次都进行push结束时间

}

return q.size();

使用优先级队列，一个小根堆，里面用来存放最早结束时间，遍历每一个任务，如果堆顶元素小于等于该任务的最早开始时间，那么就可以进行少使用一个主持人，将其弹出。

#include <climits>
#include <queue>
class Com
{
public:bool operator()(const vector<int>& left, const vector<int>& right){if(left[0] == right[0])return left[1]<right[1];elsereturn left[0]<right[0];}
};class Solution {
public:int minmumNumberOfHost(int n, vector<vector<int> >& startEnd) {// write code hereif(n==1)return 1;sort(startEnd.begin(), startEnd.end(), Com());priority_queue<int, vector<int>, greater<int>> q;q.push(INT_MIN);for(int i = 0; i < n; i++){if(q.top()<=startEnd[i][0])q.pop();q.push(startEnd[i][1]);}return q.size();}
};

【大佬使用的哈希】


class Solution {
public:int minmumNumberOfHost(int n, vector<vector<int> >& startEnd) {// write code heremap<int, int> mp;for(auto& item : startEnd){mp[item[0]]++;mp[item[1]]--;}int cur = 0;int ret = 0;for(auto& item : mp){cur += item.second;if(cur > ret)ret=cur;}return ret;}
};

【贪心】


class Solution {
public:int minmumNumberOfHost(int n, vector<vector<int> >& startEnd) {// write code herevector<int> start;vector<int> end;// 分别得到活动起始时间for(int i = 0; i < n; i++){start.push_back(startEnd[i][0]);end.push_back(startEnd[i][1]);}// 进行排序sort(start.begin(), start.end());sort(end.begin(), end.end());int res = 0;int j = 0;for(int i = 0; i < n; i++){// 新开始的节目大于上一轮结束时间，主持人不变if(start[i] >= end[j])j++;elseres++;}return res;}
};