主題
題目連結：
題目意譯：
我們有 n 件工作，其中每一件工作之排程為開始於 startTime[i] 並結束於 endTime[i]，並得到 profit[i] 之利潤。
你被給定 startTime 、 endTime 和 profit 之陣列，回傳你最大可獲得的利潤，使得你選出的工作子集合之中沒有兩件工作的時間有所重疊。
如果你選擇了一件結束於時間點 X 的工作，則你可以選擇開始於時間點 X 的另一件工作。
限制：
1 ≦ startTime.length == endTime.length == profit.length ≦ 5 × 10 ^ 4
1 ≦ startTime[i] < endTime[i] ≦ 10 ^ 9
1 ≦ profit[i] ≦ 10 ^ 4
範例測資：
範例 1：
輸入： startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]
輸出： 120
解釋： 選定之子集合為第一件與第四件工作。
時間範圍為 [1-3]+[3-6]，我們得到利潤 50 + 70 = 120。
範例 2：
輸入： startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,70,60]
輸出： 150
解釋： 選定之子集合為第一件、第四件與第五件工作。
我們得到利潤 20 + 70 + 60 = 150。
範例 3：
輸入： startTime = [1,1,1], endTime = [2,3,4], profit = [5,6,4]
輸出： 6
解題思維：
假設我們執意要做某一件工作 t（其開始於 s，結束於 e），且 t 是我們最後一個做的工作（即不會有工作開始於 e 之後）。則可以看到以 t 為準的最佳解會是：
「所有結束時間 ≦ s 的工作之最佳解」+「t 的利潤」
可以看到這個「架構」至少會消掉 t 本身來形成一個新的子問題，並且自身的最佳解是基於該子問題而得到，因此可以看到本題有最佳子結構（Optimal Substructure）。而動態規劃（Dynamic Programming，DP）之精神便是基於最佳子結構。
現在重寫一下上面的架構——定義一陣列 D，其中 D[i] 代表著在工作 i 作為最後一件工作完成（即不存在其餘完成的工作 i' 使得 endTime[i] ≦ startTime[i']）的情況下，所能得到的最大利潤。而其遞迴式為：
D[i] = Q(J) + profit[i]，其中 J 為所有 endTime[j] ≦ startTime[i] 的工作 j 形成之集合，而 Q(J) 為這些工作之最佳解。
可以看到如果現在多新增一個利潤 0 且開始時間為正無限大的工作，其對應的工作集合 J' 即是原本的 n 件工作。因此所求即為 Q(J')。
因此現在我們需要一個變數 M，用來代表著現在看到所有結束時間小於等於某個特定時間 T 的那些工作之最佳解。這樣一來，之後遇到開始時間 ≧ T 的工作時，便知道其子問題的最佳解，因此直接代入 M 即可。
所以我們還需要一個方式來把所有工作的時間順序找出來，而這個方式實際上就是掃描線演算法（Sweep Line Algorithm），參見這題。所以每一個工作的時間端點現在都會用一個三元組 (i, j, k) 所表示，其中 i 為時間值、j 代表著這是工作開始還是結束（由於同一時間點，可以接續剛結束的工作並開始下一個，因此「開始」應為較大的數字、「結束」應為較小的數字），而 k 則代表著工作原本的索引值。
將這些端點按照各個元素值由小排到大後，我們便可以開始掃過這些端點來求解並維護上述提及的變數 M 之值：
當遇到「開始」時，則將 D[k] 之值設為 M + profit[k]；
當遇到「結束」時，則將 M 之值設為 max(M, D[k])。
最後的 M 值即為所求。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
