問題描述:活動安排問題--貪心算法
有11項考試要安排,每項活動 i 的開始時間為
(start),結束時間為
(finish)
問在規定的時間内最多可安排多少項活動?
具體實作代碼及詳細注釋
public class ActivityArrange {
/*
解決方案代碼:
i 表示 第i個活動
s[i] 表示 第i個活動的開始時間
f[i] 表示 第i個活動的結束時間
a[i] 是否選擇安排第i個活動(true代表是,false代表否)
*/
public static void greedySelector(int[] s, int[] f, boolean[] a)
{
a[1] = true; // 選擇安排活動1
int j = 1; // 記錄最近一次的活動序号
int count = 1; // 總的可以安排的活動數
int n = s.length - 1;
for(int i=2; i<=n; i++) // 依次檢查其餘每一項活動與已選擇的活動的相容性
{
if(s[i] >= f[j]) // 如果第i項活動相容
{
a[i] = true; // 選擇安排第i項活動
j = i; // 記錄最近一次的活動序号
count++; // 總的可以安排的活動數加1
}
else // 如果不相容
a[i] = false; // 選擇不安排第i項活動
}
// 列印 活動安排情況,安排的數量
for (int i=1; i<a.length; i++)
System.out.println("A" + i + " = " + a[i]);
System.out.println("總的活動數量 = " + count);
}
public static void main(String[] args)
{
// 定義11項活動的開始時間,結束時間(按升序排序)
int[] s = {0,1,3,0,5,3,5,6, 8, 8, 2, 12};// s[0]不用
int[] f = {0,4,5,6,7,8,9,10,11,12,13,14};// f[0]不用
boolean[] a = new boolean[12];// a[0]不用
// 調用貪心算法 安排活動 并 計算最大可安排數量
greedySelector(s, f, a);
}
}