基础训练之“贪心”

BM96 主持人调度（二）

题意：有n个活动，每个活动都有开始时间和结束时间，且都需要一个主持人来主持。每个主持人同一时间只能主持一个活动，问最少需要多少主持人才能把所有活动圆满举办。

题解：这个解法算是比较好理解的做法了，但理解起来还是有点麻烦。

1. 首先对活动的开始时间从小到大进行排序，意味着所有活动按时间顺序进行。
2. 设立一个小根堆（使用优先队列这一数据结构）维护正在举行活动的结束时间，也就是说小根堆里活动的个数代表着现在主持人的个数（每个活动都需要一个主持人）。
3. 每当要新举行一个活动时，我们将这个新活动的开始时间和推顶活动的结束时间进行比较。
4. 如果新活动的开始时间大于堆顶活动的结束时间，说明当主持人在举行完堆顶的这个活动后马上可以接着来举行这个新活动，将堆顶活动删除，加入新活动的结束时间。最大化利用了主持人，这里保证了需要的主持人最少。
5. 如果新活动的开始时间小于堆顶活动的结束时间（比堆顶都小，那就比所有活动的结束时间都小），说明当前时间点所有主持人都在举行活动，需要增加一名主持人，将新活动的结束时间放入堆。这里保证了每个活动的执行。
6. 所以可以这么理解，题目意思是要将n个活动分成m组，组内的时间区间不能重合。而我们做的是，用小根堆维护这些组内的某一个活动。所以到最后一定会有m个活动在堆里，代表着m个小组。
7. 代码如下所示

   class Solution {
   public:
       int minmumNumberOfHost(int n, vectorint> >& startEnd) {
           sort(startEnd.begin(), startEnd.end(), [](const vector<int> &s1, const vector<int> &s2){
               if(s1[0] != s2[0]) return s1[0] < s2[0];
               else return s1[1] < s2[1];
           });//活动时间排序
           priority_queue<int, vector<int>, greater<int> > que;//小根堆，存入正在举行活动的结束时间
           que.push(INT_MAX);//先存入最大值，保证第一个活动进来时需要新增一个主持人
           int num = 0;
           for(auto S : startEnd) {//遍历各个活动
               if(S[0] >= que.top()) {//比较
                   que.pop();
               } else {
                   num++;
               }
               que.push(S[1]);
           }
           return num;
       }
   };