活動安排問題

描述

活動安排問題是可以使用貪心算法有效求解的很好的例子。

設有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相容。活動安排問題就是要在所給的活動集合中選出最大的相容活動子集合。