当前位置: 代码迷 >> 综合 >> 活动选择问题 oj
  详细解决方案

活动选择问题 oj

热度:60   发布时间:2024-01-14 22:40:19.0

活动选择问题

Time Limit: 1000 ms  Memory Limit: 65536 KiB
Submit  Statistic
Problem Description
sdut 大学生艺术中心每天都有n个活动申请举办,但是为了举办更多的活动,必须要放弃一些活动,求出每天最多能举办多少活动。
Input
输入包括多组输入,每组输入第一行为申请的活动数n(n<100),从第2行到n+1行,每行两个数,是每个活动的开始时间b,结束时间e;
Output
输出每天最多能举办的活动数。
Sample 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
Sample Output
5
Hint
Source
#include<stdio.h>  struct node  
{  int start;  int end;  int select;  int id;  
}a[100],temp;  int main()  
{  int n;  int i,j;  int s;  while(~scanf("%d",&n))  {  s = 0;  for( i = 0; i < n; i++ )  {  scanf("%d%d",&a[i].start,&a[i].end);  a[i].id = i + 1;  a[i].select = 0;  }  for( i = 0; i < n - 1; i++ ) {  for( j = 0; j < n - i - 1; j++ ) {  if( a[j].end > a[j+1].end ) {  temp = a[j];  a[j] = a[j+1];  a[j+1] = temp;  }  }  }  for( i = 0; i < n; i++ ) {  if( a[i].start >= s ) {  a[i].select = 1;  s = a[i].end;  }  }  ///统计事件的个数,并输出结果  s = 0;  for( i = 0; i < n; i++ )  {  if( a[i].select == 1 )  s++;  }  printf("%d\n",s);  }  return 0;  
} 
  相关解决方案