I--免费看电影

I--免费看电影

时间： 1ms        内存：128M

描述：

万象城星美影院开业1周年了，要举行为期一天的大酬宾，ACM队员准备去看电影。已知电影院的播放电影的各个时间阶段。要求ACM队员如何安排自己的时间，使得看的电影场次最多。

输入：

测试数据第一行为n(n>=0)，表示电影的场次；接着是n行，每行有两个整数，表示每场电影开始时间与结束时间。

输出：

输出ACM队员最多能看的电影场次。

示例输入：

11
11 14
13 15
12 14
12 13
8 10
15 17
14 18
15 19
18 22
18 21
16 20

示例输出：

5

提示：

参考答案（内存最优[1092]）：

#include<stdio.h>
typedef struct  movie {
int sta,end,flag;
}movie;
int max=0,n;
void watch(movie a[],int time,int k)
{
    int i;
    if(k>=max) max=k;
    for(i=1;i<=n;i++)
        if(a[i].sta>=time)
    {
        a[i].flag=1;
        watch(a,a[i].end,k+1);
        a[i].flag=0;
    }
    return ;
}
int main()
{

   int i;
   movie a[1000];
   scanf("%d",&n);
   for(i=1;i<=n;i++)
    scanf("%d%d",&a[i].sta,&a[i].end),a[i].flag=0;
   watch(a,0,0);
   printf("%d",max);
   return 0;
}

参考答案（时间最优[0]）：

#include <iostream>
#include <algorithm>
using namespace std;

struct node
{
    int start,end;
}Node[1000];

int cmp(node n1,node n2)
{
    if(n1.end<=n2.end)return 1;
    else return 0;
}

int main()
{
    int n;
    cin>>n;
    if(n==0)
    {
        cout<<0<<endl;
    }
    else
    {
        for(int i=0;i<n;i++)
        {
            cin>>Node[i].start>>Node[i].end;
        }
        sort(Node,Node+n,cmp);
        int j=0,sum=1;
        for(int i=1;i<n;i++)
        {
            if(Node[i].start-Node[j].end>=0)
            {
                j=i;sum++;
            }
        }
        cout<<sum<<endl;
    }
    return 0;
}

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