一、Interval Scheduling
初學算法設計與分析，老師就講到了這個比較難的問題，聽的時候就似懂非懂。現在搞清楚記錄如下。
本問題涉及到的算法：貪心算法（Greedy Algorithm）
1.1 問題描述：
假設我們有多個任務，圖中給出了，每個任務的開始時間和終止時間。不同任務不重疊的情況下，求任務的最大組合數。
input:具有起始時間(Si)和終止時間(Fi)的任務集合
goal：不同任務的最大組合數
1.2 問題分析：
分析一個問題，我們首先分析出一個可行的算法，然後再對算法進行優化，盡可能降低複雜度，達到最優的情況。
備選方案：
1、任務按開始時間排序(Si)；
2、任務按終止時間排序(Fi)；
3、任務按照所用時間長短(Fi - Si)排序;
4、對于每一個任務，計算與它沖突的任務個數Ci，然後對Ci排序。
由于本問題比較簡單，我們不過多讨論。容易發現，使用貪心算法，我們按照終止時間排序，可以成功的求解問題。
1.3 問題求解：
首先我們按照終止時間，對任務進行排序，然後依次選擇，不重疊的任務，即可求出，最大的任務組合數。
僞代碼：
Sort jobs by finish times so that f1 <= f2 <= ... <= fn.
select a task ——>A
for j = 1 to n {
if (job j compatible with A)
A and {j} ——> A
}
return A
算法複雜度：O(n logn)
其實這個問題是有别的算法的，我們課上同學讨論出一個，老師都驚呆了。老師本來想推翻同學的算法，結果發現，同學的算法非常正确。
二、Weighted Interval Scheduling
在問題一的基礎上，稍加修改，問題變難很多，成為帶權值的任務排程問題。上課睡覺的後果就是，課上成功聽不懂，課下自己想辦法。
本問題涉及到的算法：動态規劃（Dynamic Programming）
講真提到動态規劃，比較頭大，尤其是對于沒有算法的基礎新手。在此貼上知乎大佬的解釋：https://www.zhihu.com/question/23995189
2.1 問題描述：
在問題1的基礎上，我們對每個任務增權重值。實際情況下，我們可以認為，我們的任務優先級不同，重要性不同。即使有些任務，用到的時間短，重要性卻很高。在這種情況下，我們求解，固定時間内，求完成任務權值和的最大值。
input:具有起始時間(Si)，終止時間(Fi)和權值(Wi)的任務集合
goal：任務組合的權值最大值
2.2 問題分析：
首先我們考慮貪心算法，能否用于本問題。容易發現，問題1其實是問題2的權值為1的特例，在權值為1的情況下，貪心算法是可以求解的。若權值是任意值，算法便會失效。從圖中我們可以看出，任務b的權值很大，卻不會被選出，明顯權值和，不是最大。
這裡直接說算法，求解吧，畢竟我也不知道到底是怎麼想出來的。前人的經驗，我們看懂，了解，也算成功了。
2.2 問題求解：
當然，本問題，是可以暴力求解的，也就是枚舉(周遊)，但這必然複雜度，爆炸，如果都用枚舉，我們還學算法有毛用。
這裡還需要說下，有兩種算法，一種是使用回歸算法，另一種Bottom to Up
直接上算法，稍後再解釋。
###2.2.1回歸算法：
sort：首先我們按照結束時間對任務進行排序；
define：定義一個函數P(i)，是指與任務i不重疊的索引最大值，該索引小于i；
OPT(j)=max(Wj+OPT(p(j)),OPT(j−1))
算法僞代碼：
首先我們對任務按結束時間排序，這裡就不多說了。然後我們定義了一個函數P(i)，是指與任務i不重疊的索引最大值，該索引小于i。比如說下圖：
當i=8，P(8)也就是，與任務8不重疊的任務索引的最大值，從圖中看出是5，是以P(8)=5。
然後我們定義OPT(i)也就是，對于i個任務，該問題的最優解的值。對于j個任務的最優解，我們按照是否選擇任務j，可以劃分為兩種情況。**情況一：**選擇任務j，取它的權值Wj，然後往前找與任務j不重疊的任務索引最大值，求OPT(P(j))，然後将二者相加；**情況二：**不選擇任務j，選擇任務j-1。然後我們比較這兩種情況的大小，作為j個任務的最優解。
算法缺陷：
當我們有大量的子問題的時，回歸算法需要大量的計算，成為指數問題，算法便會失效。
其實我們這個算法，是從任務的最後一個，依次向前求，需要不停地回歸，用到前面的值，同時我們需要不停地存儲最優解。
###2.2.2 ：Bottom-up dynamic programming
從公式我們可以看出每一個OPT值依賴于前一個值，OPT(p(j))或者是OPT(j-1)。是以，我們能否倒過來，将n的順序，也就是從第一個開始開始，計算OPT(j)的值呢。實際是我們是可以的，也就是按照下圖給出的僞代碼。
僞代碼：
強烈建議看下這個網站：https://farazdagi.com/2013/weighted-interval-scheduling/
除了詳細的解釋，還有python的代碼實作，而且詳細的解釋了，具體每一步的複雜度。
參考資料：
1.http://www.tceic.com/3l9850lg1711ii7930h71614.html
2.https://www.daniweb.com/programming/software-development/threads/449426/weighted-interval-scheduling
3.https://en.wikipedia.org/wiki/Interval_scheduling
4.https://farazdagi.com/2013/weighted-interval-scheduling/