HDOJ2037——今年暑假不AC

问题描述

给定一天内许多节目的开始时间Ti_s和结束时间Ti_e,求如何合理安排，使得能看尽量多的完整的节目？

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

问题分析

一开始的想法是计算每个节目的覆盖率(遮盖住其他节目的面积)。实际上非常麻烦，典型的小题大作。
采取贪心策略，对节目的结束时间进行排序，则越早结束的节目应该排在时间轴的越前面。这样的好处是只需判断下一个节目的开始时间是否落在前一个节目的时间之内就行了。如果落在上一个节目之中，那一定没法看。反之可以看。复杂度为O(N)。

代码

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
struct program
{
  int s;
  int e;
}program[101];
int cmp(const void *a,const void *b) //对结束时间进行排序
{
  struct program *aa = (struct program *)a;
  struct program *bb = (struct program *)b;
  return aa -> e > bb -> e ? 1 : -1;
}

int main()
{
  int n,i;
  while(scanf("%d",&n) != EOF && n != 0)
  {
    for(i=0;i<n;i++)
    {
      scanf("%d%d",&program[i].s,&program[i].e);
    }
    qsort(program,n,sizeof(program[0]),cmp);
    //for(i=0;i<n;i++)  printf("e = %d\n",program[i].e);
    int tail = 0,count = 0;
    for(i=0;i<n;i++)
    {
      if(program[i].s >= tail)
      {
        count++;
        tail = program[i].e;
      }
    }
    printf("%d\n",count);
  }
}