貪心算法幾個經典例子

活動安排問題] 活動安排問題是可以用貪心算法有效求解的一個很好的例子。該問題要求高效地安排一系列爭用某一公共資源的活動。貪心算法提供了一個簡單、漂亮的方法使得儘可能多的活動能相容地使用公共資源。

設有n個活動的集合e={1，2，…，n}，其中每個活動都要求使用同一資源，如演講會場等，而在同一時間內只有一個活動能使用這一資源。每個活動i都有一個要求使用該資源的起始時間si和一個結束時間fi，且si< fi。如果選擇了活動i，則它在半開時間區間[si，fi]內佔用資源。若區間[si，fi]與區間[sj，fj]不相交，則稱活動i與活動j是相容的。也就是說，當si≥fi或sj≥fj時，活動i與活動j相容。活動安排問題就是要在所給的活動集合中選出最大的相容活動子集合。

在下面所給出的解活動安排問題的貪心算法gpeedyselector中，各活動的起始時間和結束時間存儲於數組s和f{中且按結束時間的非減序：．f1≤f2≤…≤fn排列。如果所給出的活動未按此序排列，我們可以用o(nlogn)的時間將它重排。