说实话开始没做出来。就是没想到怎么转换,甚至别人的题解开始都没看懂,看了好几遍。
换种思路来考虑这个问题。
寻找题目的规律,假设全部活动安排好了,主持人也根据题目的情况刚好到位了。寻找第N个活动的情况跟前N-1个活动的关系。
问题:
1.第N个活动是否需要新增主持人。
2.前面有多少个主持人。
3.不需要新增,那最好是前面N-1个活动的,那一个(或哪几个之一)活动的主持人。
解答:需要判断第N个活动的开始时间,前N-1个活动中最早结束的活动。
如果比最近一个活动时间大,就不需要增加主持人,反之需要增加主持人。
注意:不增加主持人时,需要前一个最早的活动结束时间从列表后移,因为这个主持人的活动结束时间更新了。
那么:判断时间上第N个活动,比较好处理,把活动的开始时间排序,第N个活动就是排序后的第N个。
前N-1个活动的最近一个活动的结束时间怎么处理。
把所有活动的结束时间排序。取最早结束的活动。如果最早的结束时间在第N个活动之前,那么这个活动一定是前N-1个活动,而且不需要增加主持人,。
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 num = 0;
vector<int> start;
vector<int> end;
for(int i=0;i<startEnd.size();i++){
start.push_back(startEnd[i][0]);
end.push_back(startEnd[i][1]);
}
sort(start.begin(), start.end());
sort(end.begin(), end.end());
int j=0;
for(int i=0;i<start.size();i++){
if(start[i] < end[j]){
num ++;
}else{
j++;
}
}
return num;
}
};



京公网安备 11010502036488号