活动安排问题（贪心算法）

活动安排问题（贪心算法）

1. //活动安排问题  
2.  
3. public class Activearr 
4. { 
5.     public static int greedselector(int [] s,int [] f,boolean [] a) 
6.     { 
7.         int n = s.length - 1; 
8.         a [0] = true; 
9.         int j = 1; 
10.         int count = 1; 
11.          
12.         for (int i = 1;i <= n;i ++) 
13.         { 
14.             if (s [i] >= f [j]) 
15.           { 
16.             a [i] = true; 
17.             j = i; 
18.             count ++; 
19.                
20.           }   
21.           else a [i] = false; 
22.                  
23.         } 
24.          
25.         return count; 
26.      
27.     } 
28.     public static void main(String args []) 
29.     { 
30.         int count; 
31.         int s [] = {1,3,0,5,3,5,6,8,8,2,12}; 
32.         int f [] = {4,5,6,7,8,9,10,11,12,13,14}; 
33.         boolean a [] = new boolean [11]; 
34.          
35.         Activearr aa = new Activearr(); 
36.         count = aa.greedselector(s,f,a); 
37.         System.out.println("共有" + count + "活动可以举行:"); 
38.         System.out.println(); 
39.         for (int i = 0;i <= 10;i ++) 
40.            if (a [i] == true) 
41.               System.out.println("第" + i + "活动可以举行"); 
42.                
43.     } 
44.            
45. } 

活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合，是可以用贪心算法有效求解的很好例子。该问题要求高效地安排一系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动能兼容地使用公共资源。

设有n个活动的集合E={1,2,…,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si <fi 。如果选择了活动i，则它在半开时间区间[si, fi]内占用资源。若区间[si, fi]与区间[sj, fj]不相交，则称活动i与活动j是相容的。也就是说，当si≥fj或sj≥fi时，活动i与活动j相容。