posts - 99,  comments - 8,  trackbacks - 0
hdu 2037

简单的贪心题：只需要将结束时间利用qsort进行排序后，贪心准则应当是：在未安排的活动中挑选结束时间最早的活动安排，
好给后面的活动安排留出更多的空间，从而达到安排最多活动的目标。 加上一个判断条件就可以搞定了

 1#include <stdio.h>
 2#include <stdlib.h>
 3struct time
 4{
 5    int start; 
 6    int end;
 7}a[100];
 8
 9int cmp (const void *a, const void *b)
10{
11    return (*(time *)a).end - (*(time *)b).end;
12}
13
14int main ()
15{
16    int n;
17    while (scanf ("%d", &n) != EOF && n != 0)
18    {
19          for (int i = 0; i < n; i ++)
20          {
21              scanf ("%d %d", &a[i].start, &a[i].end);
22          }
23          //对结束时间进行从小到大的排序
24          qsort (a, n, sizeof (a[0]), cmp); 
25          
26          int count = 1;
27          int temp = 0;
28          for (int i = 1; i < n; i ++)
29          {
30              if (a[i].start >= a[temp].end)
31              {
32                 temp = i;
33                 count ++;                 
34              }                
35          }
36          
37          printf ("%d\n", count);
38    }
39    //system ("pause");
40    return 0;
41}
42


 

posted on 2010-08-22 21:04 雪黛依梦 阅读(782) 评论(0)  编辑 收藏 引用 所属分类: 背包----贪心、回溯、分支界限

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


Copyright ©2024 雪黛依梦 Powered By: 博客园 模板提供：沪江博客
<2024年7月>
日一二三四五六
30123456
78910111213
14151617181920
21222324252627
28293031123
45678910

常用链接

留言簿(4)

随笔分类

随笔档案

文章档案

搜索

  •  

最新评论

阅读排行榜

评论排行榜