活动选择问题

TimeLimit: 1000MS Memory Limit: 65536KB

SubmitStatistic

Problem Description

 sdut 大学生艺术中心每天都有n个活动申请举办，但是为了举办更多的活动，必须要放弃一些活动，求出每天最多能举办多少活动。

Input

 输入包括多组输入，每组输入第一行为申请的活动数n(n<100)，从第2行到n+1行，每行两个数，是每个活动的开始时间b，结束时间e；

Output

 输出每天最多能举办的活动数。

Example Input

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

Example Output

5

Hint

 

Author

 

 

 

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
struct node
{
    int i,a,b;


}c[101];


int cmp( const void*a,const void*b)
{
   struct node*c = (node*)a;
   struct node*d = (node*)b;

  return c->b - d->b;
}
int main()
{

  int n;
  while(~scanf("%d",&n))
  {



  for(int i=1;i<=n;i++)
  {
        scanf("%d%d",&c[i].a,&c[i].b);

  }
  qsort(&c[1],n,sizeof(c[1]),cmp);
int   k = 1,u =1;

  for(int m=2;m<=n;m++)
  {
      if(c[m].a>=c[k].b)
      {
         u++;
         k = m;
      }

  }
  printf("%d\n",u);





  }



  return 0;

}


/***************************************************
User name: jk160505徐红博
Result: Accepted
Take time: 0ms
Take Memory: 108KB
Submit time: 2017-01-11 21:05:40
****************************************************/