贪心算法(最大兼容子序列)

1. 题目描述：  
2. 又到毕业季，很多大公司来学校招聘，招聘会分散在不同时间段，小明想知道自己最多能完整的参加多少个招聘会(参加一个招聘会的时候不能中断或离开)。  
3. 输入：  
4. 第一行n，有n个招聘会，接下来n行每行两个整数表示起止时间，由从招聘会第一天0点开始的小时数表示。  
5. n <= 1000 。  
6. 输出：  
7. 最多参加的招聘会个数。  
8. 样例输入：  
9. 3  
10. 9 10  
11. 10 20  
12. 8 15  
13. 样例输出：  
14. 2  
15. 这个问题是对几个相互竞争的招聘会活动进行调度，它们都要求以独占的方式使用某一公共资源（小明）。调度的目标是找出一个最大的相互兼容的活动集合。这里是有一个需要使用某一资源（小明）的n个活动组成的集合S={a1,a2,...,an}.该资源一次只能被一个活动占用。每个活动ai有开始时间si和结束时间fi，且0<=si<fi<无穷。一旦被选择后，活动ai就占据了区间[si,fi].如果区间[si,fi]和[sj,fj]互不重叠，称活动ai和aj是兼容的。活动选择问题就是要选择出一个由互相兼容的问题组成的最大子集合。
    将所有的活动按照结束时间升序排列

    i	1	2	3
    si	9	8	10
    fi	10	15	20

    
    

    定理

    对于任意非空子问题Sij，设am是Sij中具有最早结束时间的活动：
    fm=min{fk:ak属于Sij}
    那么，
    1）活动am在Sij的某最大兼容活动子集中被使用
    2）子问题Sim为空，所以选择am将使子问题Smj为唯一可能非空的子问题

1. #include <stdio.h>   
2. #include <stdlib.h>   
3. #include <string.h>   
4.    
5. struct join  
6. {  
7.     int begin;  
8.     int end;  
9. };  
10.    
11. int compare(const void *a, const void *b);  
12.    
13. int main()  
14. {  
15.     int i, n, k;  
16.     struct join joins[1001], temp[1001];  
17.    
18.     while(scanf("%d", &n) != EOF)  
19.     {  
20.         for(i = 0; i < n; i ++)  
21.         {  
22.             scanf("%d %d", &joins[i].begin, &joins[i].end);  
23.         }  
24.            
25.         qsort(joins, n, sizeof(joins[0]), compare);  
26.    
27.         k = 0;  
28.         temp[k] = joins[0];  
29.         for(i = 1; i < n; i ++)  
30.         {  
31.             if(joins[i].begin >= temp[k].end)  
32.                 temp[++ k] = joins[i];  
33.         }  
34.         printf("%dn", k + 1);  
35.     }  
36.        
37.     return 0;  
38. }  
39.    
40. int compare(const void *a, const void *b)  
41. {  
42.     const struct join *p = a;  
43.     const struct join *q = b;  
44.    
45.     return p->end - q->end;  
46. }  
47. /************************************************************** 
48.     Problem: 1463 
49.     User: wangzhengyi 
50.     Language: C 
51.     Result: Accepted 
52.     Time:10 ms 
53.     Memory:904 kb 
54. ****************************************************************/  

最后

以上就是朴实音响为你收集整理的贪心算法(最大兼容子序列)的全部内容，希望文章能够帮你解决贪心算法(最大兼容子序列)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。