说实话开始没做出来。就是没想到怎么转换,甚至别人的题解开始都没看懂,看了好几遍。
换种思路来考虑这个问题。
寻找题目的规律,假设全部活动安排好了,主持人也根据题目的情况刚好到位了。寻找第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; } };