51nod 1428活动安排问题

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

 收起

输入

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

输出

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

输入样例

3 1 2 3 4 2 9

输出样例

2

分析：

这题受到了这题的影响：​​51nod 1133 不重叠的线段​​

这题要看好题意，主要思想就是我们按照从小到到排序，左端点优先，右端点其次

我们用一个优先队列保存我们选择的活动的结束时间最早的一个，如果当前活动的开始时间<=q.top(),这个活动可以接在后面，然后更新优先队列；如果当前活动的开始时间>q.top(),肯定要为它新开一个教室

#include<bits/stdc++.h>
using namespace std;
struct node
{
  long long l,r;
}a[100005];
bool cmp(node x,node y)
{
  if(x.l==y.l)
    return x.r<y.r;
  
  return x.l<y.l;
}
int main()
{
  int n;
  while(~scanf("%d",&n))
  {
    priority_queue<long long,vector<long long>,greater<long long> >q;
    
    for(int i=1;i<=n;i++)
    {
      scanf("%lld%lld",&a[i].l,&a[i].r);
      
    }
    sort(a+1,a+n+1,cmp);
    long long ans=1;
    long long last=a[1].r;
    q.push(a[1].r);
    for(int i=2;i<=n;i++)
    {
       if(a[i].l<q.top())
       {
        ans++;
        q.push(a[i].r);
       }
       else
       {
        q.pop();
        q.push(a[i].r);
       }
    }
    printf("%lld\n",ans);
    
  }
  return 0;
}