会场安排问题
发布时间
阅读量：
阅读量
会场安排问题
时间限制： 3000 ms | 内存限制： 65535 KB
难度： 4
学校的礼堂经常 hosting各种各样的文化与学术活动，在不同的时间段内这些活动中可能会出现时间上的重叠情况；在这种情况下就需要从众多活动中筛选出部分进行安排以避免冲突。作为负责管理礼堂空间使用的副校长小李需要根据预定的时间表合理规划每一天的工作任务；他希望能够在有限的时间与空间内最大限度地满足尽可能多的需求；请问您认为他应该采取什么样的具体措施来实现这一目标呢？
输入部分的第一行是一个整型变量m（m<100）表示共有m组测试数据。每组测试数据的第一行是一个整数n（1<n<100），表示该测试数据包含n个活动。随后的n行为两个正整数Bi、Ei（其中Bi≤Ei）所表示的时间区间。
输出 对于每一组输入，输出最多能够安排的活动数量。
每组的输出占一行
样例输入
样例输出
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int a[10005][2];
int i,j,sum,m,n;
struct node{
int a,b;
}c[10005];
bool rmp(node x,node y){
return x.b<y.b;
}
int main()
{
cin>>m;
while(m--)
{
cin>>n;
for(i=0;i<n;i++)
{
scanf("%d%d",&c[i].a,&c[i].b);
}
sort(c,c+n,rmp);
sum=1;
i=0;j=i+1;
while(j<n)
{
if(c[j].a>c[i].b)
{
sum++;
i=j;j++;
}
else
{
j++;
}
}
printf("%d\n",sum);
}
return 0;
}全部评论 (0)
还没有任何评论哟~