NYOJ - 14：会场安排问题
发布时间
阅读量：
阅读量
会场安排问题
来源：NYOJ
标签：区间问题，贪心算法
参考资料：
相似题目：
题目
学校的小礼堂每天都会举办很多活动，在排课时由于各种活动的排课时间存在重叠情况会导致资源分配出现冲突问题为此学校行政人员小刘需要从众多活动中筛选出一部分进行实际举办工作每位时间段最多只能安排一个活动现在小刘已经整理好了各项目活动中所需排课时间他希望能够最大限度地利用现有资源请问小刘应该如何合理规划这些时间段以实现最大化利用
输入
开头是一条整数值m(m<100)，它代表了包含m组测试用例的数据量。
每个测试用例的第一部分是一个数值n(1 < n < 1e4)，表明该用例包含了n个活动项。
接下来的每一行为两个正整数值Bi和Ei（其中 Bi <= E_i），它们分别代表第i个活动的时间段起点和终点时间。
输出
对于每一组输入，输出最多能够安排的活动数量。
每组的输出占一行
输入样例
2
2
1 10
10 11
3
1 10
10 11
11 20
输出样例
1
2
参考代码
#include<stdio.h>
#include<algorithm>
#define MAXN 10005
using namespace std;
struct Interval{
int a;
int b;
}interval[MAXN];
bool cmp(Interval x, Interval y){
return x.b<y.b;
}
int main(){
int m;
scanf("%d",&m);
while(m--){
int n;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d%d",&interval[i].a,&interval[i].b);
}
sort(interval,interval+n,cmp);
int cnt=0;
int start=0;
int j=0;
while(j<n){
if(interval[j].a>=start){
cnt++;
start=interval[j].b+1;
}
j++;
}
printf("%d\n",cnt);
}
return 0;
}全部评论 (0)
还没有任何评论哟~