51Nod_1428 活动安排问题【贪心】

本文主要是介绍51Nod_1428 活动安排问题【贪心】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

                                      51Nod_1428 活动安排问题

                                  http://www.51nod.com/Challenge/Problem.html#!#problemId=1428

 

 

题目

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

输入

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

输出

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

样例输入

3
1 2
3 4
2 9

样例输出

2

分析

先对活动进行排序，越早开始的活动排在前面，开始时间相同时，先结束的活动排在前面 。由于每个活动都要进行，因此使用一个优先队列endtime，它存放各个教室活动的最晚结束时间，值越小越优先。当对活动i进行安排时，如果它的开始时间小于队头教室的最晚结束时间，那么已有的教室都不能安排活动i，必须重新再开一个教室，同时需要将这个教室活动最晚结束时间存入优先队列endtime中；否则，如果它的开始时间大于等于队头教室的最晚结束时间，那么就要将队头出队，把此活动的结束时间压入队列中，即为将活动安排在队头教室中，安排后此教室活动的最晚结束时间就是此活动的结束时间了。

C++程序

#include<iostream>
#include<algorithm>
#include<queue>using namespace std;const int N=10010;struct Activity{int s,e;//越早开始的活动排在前面，开始时间相同时，先结束的活动排在前面 bool operator <(const Activity &p)const{return s==p.s?(e<p.e):(s<p.s);}
}a[N];int main()
{int n,ans=0;priority_queue<int,vector<int>,greater<int> >endtime;//存放各个教室活动的最晚结束时间 scanf("%d",&n);for(int i=0;i<n;i++)scanf("%d%d",&a[i].s,&a[i].e);sort(a,a+n);//排序for(int i=0;i<n;i++){if(endtime.empty()||a[i].s<endtime.top()){ans++;//增加一个教室，将活动i安排在此教室进行 endtime.push(a[i].e);//存入此教室活动的最晚结束时间}else{//此教室活动的最晚结束时间变为a[i].eendtime.pop();endtime.push(a[i].e); }}printf("%d\n",ans);return 0;
}

 

这篇关于51Nod_1428 活动安排问题【贪心】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---