题解 | #主持人调度#
主持人调度
http://www.nowcoder.com/practice/4edf6e6d01554870a12f218c94e8a299
说实话开始没做出来。就是没想到怎么转换，甚至别人的题解开始都没看懂，看了好几遍。
换种思路来考虑这个问题。
寻找题目的规律，假设全部活动安排好了，主持人也根据题目的情况刚好到位了。寻找第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;
}
};
三环集团开奖73人在聊
开发你这个也没有项目啊
