基准时间限制：1 秒 空间限制：131072 KB 分值: 10 

 收藏

 关注

有若干个活动，第i个开始时间和结束时间是[Si,fi)，同一个教室安排的活动之间不能交叠，求要安排所有活动，最少需要几个教室？ 

Input

第一行一个正整数n (n <= 10000)代表活动的个数。第二行到第(n + 1)行包含n个开始时间和结束时间。开始时间严格小于结束时间，并且时间都是非负整数，小于1000000000

Output

一行包含一个整数表示最少教室的个数。

Input示例

31 23 42 9

Output示例

2

 

 

贪心 + 堆

按开始时间排序 

加入一个结束时间

若开始时间时间比堆顶早 那么多加一个教室

否则 结束该活动 准备下一个活动

#include 
      
       #include 
       
        #include 
        
         using namespace std;struct Node{    int Si,Fi,Limit;    bool operator<(Node a)    {        return Si
         

,greater

>q; q.push(Activity[1].Fi); for(int i=2;i<=n;i++) { if(Activity[i].Si