主題
題目連結(jié)：
題目意譯：
我們有 n 個(gè)工作，其中每個(gè)工作之時(shí)程排為從 startTime[i] 到 endTime[i] 完成，得到 profit[i] 之利潤(rùn)。
你被給定陣列 startTime 、 endTime 和 profit，回傳你所能得到的最大利潤(rùn)使得子集合中沒(méi)有兩個(gè)工作有著重合的時(shí)間範(fàn)圍。
如果你選擇工作其結(jié)束於時(shí)間 X，則你可以在時(shí)間 X 時(shí)開(kāi)始另一份工作。
限制：
1 ≦ startTime.length == endTime.length == profit.length ≦ 5 × 10 ^ 4
1 ≦ startTime[i] < endTime[i] ≦ 10 ^ 9
1 ≦ profit[i] ≦ 10 ^ 4
範(fàn)例測(cè)資：
範(fàn)例 1：
輸入： startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]
輸出： 120
解釋： 子集合之選擇為第一與第四個(gè)工作。
時(shí)間範(fàn)圍為 [1-3]+[3-6]，我們得到利潤(rùn) 120 = 50 + 70。
範(fàn)例 2：
輸入： startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,70,60]
輸出： 150
解釋： 子集合之選擇為第一、第四與第五個(gè)工作。
得到利潤(rùn) 150 = 20 + 70 + 60。
範(fàn)例 3：
輸入： startTime = [1,1,1], endTime = [2,3,4], profit = [5,6,4]
輸出： 6
解題思維：
這題可以利用掃描線（Sweep Line）的想法（如這題）來(lái)把所有工作的時(shí)間區(qū)間貼上標(biāo)籤並按照時(shí)間數(shù)值全部由小到大排在一起。
例如有工作 X 的開(kāi)始時(shí)間是 5 、 結(jié)束於 7。那麼我們就標(biāo)記那個(gè) 5 為「開(kāi)始」、7 為「結(jié)束」。假設(shè)有另一個(gè)工作 Y 開(kāi)始於 2 結(jié)束於 5。因此所有時(shí)間點(diǎn)排在一起會(huì)是 2（Y 的開(kāi)始）、 5（Y 的結(jié)束）、 5（X 的開(kāi)始） 、 7（X 的結(jié)束）。這邊可以看到我們對(duì)於相同時(shí)間點(diǎn)的會(huì)優(yōu)先把「結(jié)束」排於前面，因?yàn)檫@兩個(gè)工作實(shí)際上根據(jù)題意是可以接著做的。
利用一個(gè)變數(shù) M 以及一個(gè)陣列 Ms，依序代表「目前」所能得到的最大利潤(rùn)（一開(kāi)始是 0）以及儲(chǔ)存如果第 i 個(gè)工作要做的話可以得到的最大利潤(rùn)。
接著我們就由小到大掃過(guò)每個(gè)時(shí)間點(diǎn)。當(dāng)遇到「開(kāi)始」時(shí)，就把該時(shí)間點(diǎn)對(duì)應(yīng)的工作索引值 i 的 Ms[i] 之值設(shè)為 M + profit[i]，因?yàn)槲覀円阎谶@個(gè)時(shí)間點(diǎn)前可以得到的最大利潤(rùn)，因此此時(shí)做工作 i 不會(huì)與前面的工作時(shí)間片段重疊到；當(dāng)遇到「結(jié)束」時(shí)，就拿該時(shí)間點(diǎn)對(duì)應(yīng)的工作索引值 i 的 Ms[i] 之值去看 M 之值比較，把 M 之值更新成較大的那方的值（也就是如果 Ms[i] 比較大，那我們就是知道做這個(gè)工作比較賺，是在這個(gè)時(shí)間點(diǎn)能獲得的最大利潤(rùn)）。
因此最後，M 之值即為所求。
此次分享到此為止，如有任何更加簡(jiǎn)潔的想法或是有說(shuō)明不清楚之地方，也煩請(qǐng)各位大大撥冗討論。
