如何選擇開燈的順序，才會讓最多燈同時亮的 ？
首先，同一盞燈不會需要開第二次。
每次開燈時間都是重新計算，所以就算你又重新開一次燈，也只會浪費前一次開燈的機會，不如開別盞燈可能讓燈亮的更多。
第二，開燈一定是連續，不然會白白浪費。
綜上所述你要在第0, 1, 2 … n-1 分鐘的時候考慮開燈的順序！
某個直覺想法是每次從關著的燈挑一個能開最久的，乍看之下蠻合理的，但有些情況把開著的燈重新計時會更好。
|
5 1 -1 -1 -1 -1 1 1 2 3 5 4 |
正解: 5 錯誤的貪心: 4 |
我們知道每盞燈持續亮著的時間，有些燈下一分鐘就關了當然不能太早開。考慮第k分鐘開燈後，目前亮著燈除了本來就開著卻還沒關掉的以外，都是前幾分鐘開的燈，第 k－1分鐘開著燈必定持續至少 2 分鐘，第 k－2秒開著燈必定持續至少 3 分鐘 …
|
e.x. 3分鐘的時候 你能開3盞燈 且持續時間可能如下: 1, 2, 3 1, 2, 5 1, 3, 6 可以保證任一個 ti ≥ i |
開 set 儲存所有可以前幾分鐘開燈的時間 (1, 2, … , inf)
如果某盞燈持續 k 分鐘 ，就將 set 中某個≤ k的數字delete，代表 前k 分鐘可以打開某盞燈並持續到現在。
期間一樣維護還開著的燈，並把關掉的燈從set中查找能不能重開且亮到現在。
ans=max(ans, 還開著的燈 +min(set中被delete的個數, 當前能開燈的數量 ) )
總時間複雜度: O(NlogN)
O(N):
對於已經開著燈他關燈的時間可以用陣列儲存
同時每次算上能持續開 k 分鐘的數量
如果數量超過目前能開的燈 那ans的上限就會降低 因為我們每分鐘只能開一盞燈 。
|
e.x. 1分鐘的時候有2個持續時間為1的燈 那我們只能選一個開 另一個也不可能之後開 所以到目前為止答案最多 n-1 2分鐘的時候有3盞燈持續時間為2的燈剛好關掉 那我們這一分鐘也只能選一個開 另外兩個同樣直接剔除 答案目前最多會只有 n - 3 |