C - 9102年啦

系统管理员 2022-03-21 07:08 174阅读 0赞

### 题目描述： ###

这都已经9102年了，杨队竟然还在看电视。 他手上有各个电视节目的开始/结束时间，请你帮忙看看他最多能在这段时间里看完几个电视节目（必须是完整的，不然杨队会觉得很不爽）  
Input  
输入数据包含多个测试实例，每个测试实例的第一行只有一个整数n(n<=100)，表示你喜欢看的节目的总数，然后是n行数据，每行包括两个数据Ti\_s,Ti\_e (1<=i<=n)，分别表示第i个节目的开始和结束时间，为了简化问题，每个时间都用一个正整数表示。n=0表示输入结束，不做处理。  
Output  
对于每个测试实例，输出能完整看到的电视节目的个数，每个测试实例的输出占一行。  
Sample Input  
12  
1 3  
3 4  
0 7  
3 8  
15 19  
15 20  
10 15  
8 18  
6 12  
5 10  
4 14  
2 9  
0  
Sample Output  
5

##### 分析： #####

这个问题是一个很经典的贪心题目。  
这个问题， 其实我们只要将每个节目按结束时间排序，从而就可以得出正确结论。  
具体贪心策略：使得剩余的时间最大化，先安排最早结束的节目为什么是这样呢？  
可能有朋友会觉得贪心策略应该是：先安排最早开始的节目，但是这样是不行的，你要是这么贪心的话，如果一个节目是最先开始的，但是它的结束时间超级超级长，那你这样贪心的话，岂不是只能安排它一个节目了吗？  
所以我们要使得剩余的时间最大化，就是先安排最早节目的活动，因为你这个节目最早结束的话，你留给其它的节目的时间就越多， 从这一方面考虑，就只能是先选择最快结束的时间了。  
在选的时候，需要注意，下一个节目开始的时间要大于等于此时所选择的节目的结束时间。

#include"stdio.h"
    #include"string.h"
    typedef struct
    {
        int start;
        int end;
    }List;
    int main()
    {
        List list[101],T;
        int N;
        int i,j,count;
        while(~scanf("%d",&N))
        {
            if(N==0)
                break;
            for(i=0;i<N;i++)
                scanf("%d%d",&list[i].start,&list[i].end);
            for(i=0;i<N-1;i++)//按结束时间排序
                for(j=i+1;j<N;j++)
                 {
                     if(list[i].end>list[j].end)
                     {
                         T=list[i];list[i]=list[j];list[j]=T;
                     }
                     else
                        if(list[i].end==list[j].end)
                          if(list[i].start<list[i].start)
                          {
                             T=list[i];list[i]=list[j];list[j]=T;
                          }
                 }
            count=1;j=list[0].end;//j保存上一次所选择的节目的结束时间
            for(i=1;i<N;i++)
            {
                if(list[i].start>=j)
                    {
                        j=list[i].end;
                        count++;
                    }
            }
          printf("%d\n",count);
        }
    }