活动选择问题
时间： 1ms 内存：128M
描述：
YTU大学生艺术中心每天都有n个活动申请举办，但是为了举办更多的活动，必须要放弃一些活动，求出每天最多能举办多少活动。
输入：
输入包括多组输入，每组输入第一行为申请的活动数n(n<100)，从第2行到n+1行，每行两个数，是每个活动的开始时间b，结束时间e。
输出：
输出每天最多能举办的活动数。
示例输入：
12
15 20
15 19
8 18
10 15
4 14
6 12
5 10
2 9
3 8
0 7
3 4
1 3
示例输出：
5提示：
参考答案（内存最优[1120]）：
#include <stdio.h>
#include <stdlib.h>
struct activity{
int b;
int e;
}act[101],temp;
int main()
{
int n,b,e,i,j,max=0,count,flag;
while(~scanf("%d",&n))
{
for(i=0;i<n;i++)
{
scanf("%d %d",&act[i].b,&act[i].e);
}
for(i=0;i<n-1;i++)
{
for(j=i+1;j<n;j++)
{
if(act[i].e>act[j].e)
{
temp=act[i];
act[i]=act[j];
act[j]=temp;
}
}
}
int cont=1;
flag=act[0].e;
for(i=1;i<n;i++)
{
if(act[i].b>=flag)
{
cont++;
flag=act[i].e;
}
}
printf("%d\n",cont);
}
return 0;
}
参考答案（时间最优[0]）：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
typedef long long LL ;
using namespace std;
inline LL lowbit(int x ){return x&(-x);}
const int inf = 0x3f3f3f3f ;
const int MAX = 10001 ;
struct node{
int b ;
int e ;
};
/*
LL sum(int x )
{
LL ans = 0 ;
while(x>0)
{
ans+=c[x] ;
x-=lowbit(x);
}
return ans ;
void updata(int i ,int d)
{
while(i<n)
{
c[i] = c[i] +d ;
x+=lowbit(x);
}
}*/
node a[MAX] ;
bool cmp(const node &a ,const node &b)
{
return a.e <b.e ;
}
int main()
{
int n ;
while(scanf("%d",&n)!=EOF)
{
for(int i = 1 ; i<=n ;i++)
{
cin >>a[i].b >>a[i].e;
}
sort(a+1,a+n+1,cmp);
int j = 0 ;
int ans = 0;
for(int i = 1 ; i<=n ;i++)
{
if(a[i].b>=a[j].e)
{
//cout<<a[i].b<<" "<<a[i].e<<endl;
j = i ;
ans++ ;
}
}
/* for(int i = 0 ; i<n ;i++)
{
cout<<a[i].b<<" " <<a[i].e<<endl;
}*/
printf("%d\n",ans);
memset(a,0,sizeof(a));
}
return 0;
}
题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。