活動安排問題（貪心算法）

1. //活動安排問題
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;
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 ++;
20. }
21. else a [i] = false;
23. }
25. return count;
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];
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 + "活動可以舉行");
43. }
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相容。