51nod1428活动安排问题（贪心+优先队列）

活动安排问题 51Nod - 1428 有若干个活动，第i个开始时间和结束时间是[Si,fi)，同一个教室安排的活动之间不能交叠，求要安排所有活动，最少需要几个教室？   Input第一行一个正整数n (n <= 10000)代表活动的个数。  第二行到第(n + 1)行包含n个开始时间和结束时间。  开始时间严格小于结束时间，并且时间都是非负整数，小于1000000000Output一行包含一个整数表示最少教室的个数。Sample Input

Sample Output

思路：

按活动开始时间大小先排序，对于每个活动，开始时间大于队首则更换队首为这个活动的结束时间，否则入队，最后队中元素的个数即为答案

代码：

#include<cstdio> #include<algorithm> #include<queue> using namespace std; struct acy {  int begin,end; }d[10005]; bool cmp(acy x,acy y) {  return x.begin < y.begin; }  int main() {  int i,n;  scanf("%d",&n);  for (i = 0;i < n;i ++)   scanf("%d %d",&d[i].begin,&d[i].end);  sort(d,d + n,cmp);  priority_queue<int,vector<int>,greater<int> > q;  q.push(d[0].end);  for (i = 1;i < n;i ++)  {   if (d[i].begin >= q.top()) q.pop(),q.push(d[i].end);   else q.push(d[i].end);  }  printf("%d\n",q.size());  return 0; }

思路：