活動參與問題 Interval Scheduling Problem

給定一系列的活動， 如何選擇才能參與最多的活動。
基本的概念是；

1. 將活動依照結束時間排序。(假設由左排到右)
2. 從最左邊開始選擇活動，每次碰到活動而且空閒就選擇，否則就跳過該活動。

    整個想法很簡單，只是我一直很納悶為什麼這樣選出來的結果就一定會是最佳解。
可能是因為我比較駑鈍但網路上也沒有多做解釋，我自己整理出來的結果大概是這樣；

    活動越早結束，也就有越大的機會可以參與下一個活動。
    但是這就產生一個問題，如果有兩個重疊的活動，其中一個長但是早結束(下圖灰)，另一個短但是晚結束(下圖紫)，這時候選擇比較早結束的也可以保證最佳解嗎？

    這時候就要想到，活動的選擇是從左邊開始選過來，所以雖然長但是早結束的活動會提早開始。也就是說如果選擇這個長的活動會導致答案並非最佳解，那代表他一定有蓋過其他活動，而且蓋過的活動必須要比它早結束(下圖藍)。否則若它依舊比較晚結束，那麼它反而會影響到後面的工作(下圖咖啡)。但因為它必須比較早結束，所以如下圖藍色與灰色，此時藍色會比灰色更早被選擇。

    所以這時候就可以理解，越早結束的活動對後面的影響越小，並不會因為它的長短而影響結果。

(如果還是沒有理解就先不要看藍色，會發現即使灰色是最長的，但它還是應該優先被選擇，因為它對後面的影響最小。但是如果藍色存在，此時就不會選擇灰色，而會選擇比它更早結束的藍色，因此越早結束越優先選擇)

簡陋參考圖

演算法筆記 -- 活動選擇問題
(Youtube) Interval Scheduling ( Greedy Algorithm ) - Algorithms
Wiki - Interval scheduling