看到的直覺可能是越早結束的越早做,但顯然會有反例,像是
時間 截止
5 6
6 7
4 8
5 9
最優解是選 4 8 和 5 9
但如果按照上面的貪心策略會選擇5 6然後就不能拿了
會出現這種問題是因為截止時間早的處理時間太久了
但不管做的時間多久,收益都是 1
那不如,如果兩個工作確定只能選一個,選做的時間越短越好,把時間留給後面的外送
於是我們可以把確定可以做的丟進資料結構裡,把不確定的(也就是上面說的兩個工作只能選一個),淘汰掉處理時間最久的一定更優
整體解法 :
按截止時間排序
掃過每個外送 有三種情況
1. 截止時間內可以處理
2. 截止時間內不能處理 但淘汰已處理的外送中花費時間最久的單子 就能夠處理
3. 淘汰已處理的外送中花費時間最久的單子 仍然沒辦法處理
這三種情況想好怎麼做就能AC了 這題的重點在狀況 2.