活动选择问题

时间: 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;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。