前往
大廳
主題

LeetCode - 1834. Single-Threaded CPU 解題心得

Not In My Back Yard | 2023-11-19 13:30:00 | 巴幣 0 | 人氣 124

題目連結:


題目意譯:
你被給定 n 個編號為 0 到 n - 1 且以一個二維整數陣列 tasks 所表示的工作,其中 tasks[i] = [enqueueTimei, processingTimei]  代表著第 i 件工作在 enqueueTimei 之後可以開始做,並且需要 processingTimei 來完成。

你現在有一個單執行緒的 CPU,其最多一次只能同時做一件工作,並且將按照以下方式運行:
如果該 CPU 目前是閒置狀態,而沒有工作可以做,則該 CPU 將維持閒置狀態;
如果該 CPU 目前是閒置狀態,而有工作可以做,則該 CPU 將會選擇完成時間最短的工作來做。如果有多件工作有著最短的完成時間,則它會選擇索引值最小者;
一旦開始做某件工作,則該 CPU 將不會停止直到把整件工作做完為止;
該 CPU 可以在完成某件工作之後馬上開始做另一件。

回傳該 CPU 處理所有工作的順序。

限制:
tasks.length == n
1 ≦ n ≦ 10 ^ 5
1 ≦ enqueueTimei, processingTimei ≦ 10 ^ 9



範例測資:
範例 1:
輸入: tasks = [[1,2],[2,4],[3,2],[4,1]]
輸出: [0,2,3,1]
解釋: 各個事件為以下:
- 在時間 = 1 時,工作 0 可以開始做了。可做工作 = {0}。
- 同時在時間 = 1 時,閒置的 CPU 開始處理工作 0。可做工作 = {}
- 在時間 = 2 時,工作 1 可以開始做了。可做工作 = {1}。
- 在時間 = 3 時,工作 2 可以開始做了。可做工作 = {1, 2}。
- 同時在時間 = 3 時,CPU 完成了工作 0 並開始處理工作 2 因為它是時間最短的。可做工作 = {1}。
- 在時間 = 4 時,第 3 工作可以開始做了。可做工作 = {1, 3}。
- 在時間 = 5 時,CPU 完成了工作 2 並開始處理工作 3 因為它是時間最短的。可做工作 = {1}。
- 在時間 = 6 時,CPU 完成了工作 3 並開始處理工作 1。可做工作 = {}。
- 在時間 = 10 時,CPU 完成了工作 1 並開始閒置。

範例 2:
輸入: tasks = [[7,10],[7,12],[7,5],[7,4],[7,2]]
輸出: [4,3,2,0,1]
解釋: 各個事件為以下:
- 在時間 = 7 時,所有工作都開始可以做了。可做工作 = {0,1,2,3,4}。
- 同時在時間 = 7 時,閒置的 CPU 開始處理工作 4。可做工作 = {0,1,2,3}。
- 在時間 = 9 時,CPU 完成了工作 4 並開始處理工作 3。可做工作 = {0,1,2}。
- 在時間 = 13 時,CPU 完成了工作 3 並開始處理工作 2。可做工作 = {0,1}。
- 在時間 = 18 時,CPU 完成了工作 2 並開始處理工作 0。可做工作 = {1}。
- 在時間 = 28 時,CPU 完成了工作 0 並開始處理工作 1。可做工作 = {}。
- 在時間 = 40 時,CPU 完成了工作 1 並開始閒置。


解題思維:
用一個優先佇列(Priority Queue)PQ 來儲存當前可以處理的工作,這樣一來便可以馬上知道時間最短的工作是哪一個。

而我們可以先將 tasks 按照 enqueueTime 由小排到大(因為所求是完成的順序,所以原本的索引值要保留),以便把已經可以放進 PQ 裡面的工作快速地找出來(即用一個指標 t 來指向「下一個」要進去的工作,直到全部工作都進到 PQ 為止)。

接著用一個變數 T 記錄「現在」的時間點(一開始 T = 0),然後就重複以下步驟直到 PQ 為空且沒有工作會再進去 PQ 為止(即 t 已經指到 tasks 的結尾):
    如果現在 PQ 為空,表示 CPU 需要閒置到下一個工作可以開始處理為止。因此將 T 設為 t 指到的工作之 enqueueTime。

    接著把現在(T 可能在第一步已經更動過了)可以開始處理的工作全部丟進 PQ 裡面。

    接著從 PQ 中拿出時間最短的工作,將其索引值丟進答案陣列中,並將 T 加上該工作的處理時間。

最後回傳負責儲存答案的陣列即可。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

相關創作

更多創作