我最近一直在學習“演算法和資料結構”課程，并且遇到了一個有趣的練習。
考慮一個具有多個a執行器、b佇列和c任務的系統。a, b,c都低于 10^5。在程式的開頭，用戶輸入了這三個數字。之后有c描述任務的行。每個任務由 3 個數字表示：到達系統的時間、它所在的佇列以及完成所需的時間。
至于系統本身，它的作業方式如下：每一秒（以時間為單位）我們必須選擇一個免費的執行者。如果超過 1 個，我們選擇編號較小的那個（每個 executor 都有一個從 1 到a）。之后，我們必須從某個非空佇列的前面選擇一個任務。如果此時有多個非空佇列等待被揀選，那么我們從當前時間最長未被揀選的佇列中揀選（例如，如果佇列1和2以及之前的佇列中有任務）我們在時間 3 從佇列 1 和時間 1 從佇列 2 獲取，然后我們從佇列 2 獲取任務）。之后，任務被分配給我們選擇的執行者，并且執行者在完成任務所需的時間內被占用。之后，他準備好接受另一項任務（他可以在完成當前任務的那一刻完成）。
所以問題的最后一個問題是每個任務列印哪個執行者將在哪個時間點處理它。
此外，對于任何輸入，該解決方案必須運行 undex 10 秒。這讓我認為它的時間復雜度必須低于 O(N^2)。所以，我正在考慮 O(N*logN) ，實際上我非常接近它。
到目前為止，我的解決方案如下：
首先我們選擇一個執行者。如果我們使用最小堆來存盤執行器，我們可以在對數時間內完成。為了比較執行者，我們可以跟蹤他們每個人在完成另一項任務后獲得空閑的時間，然后比較這些時間。如果時間相等，那么我們比較執行者的數量。一開始，每個執行者在時刻 0 都是空閑的（任務在時刻 1 開始到達）。因此，對于每個任務，我們都可以選擇一個首先準備好的執行器。
我們還可以注意到，在任何給定的時間點，我們不需要所有佇列中的所有任務，只需要每個佇列前面的任務。我們可以將它們存盤在一個陣列中，我們稱之為tasksArray。
因此，我們可以遍歷每個佇列，如果前面的任務在選擇的執行程式釋放之前到達，那么我們將該任務存盤在一個單獨的陣列中。該陣列將包含所選執行者一旦從其先前的任務中解脫出來就能夠執行的所有任務。
如果沒有找到任務，則意味著執行者必須等到一些任務到來。為了確定這些任務將是哪些，我們可以再次遍歷所有佇列并找到最快到達的任務。可能有多個任務（2 個任務可能同時到達不同的佇列），所以我們將它們存盤為一個陣列。
兩種描述的挑選任務的方式都是 O(N)。到目前為止，它似乎還可以。
使用上述方法之一選擇任務后，我們可以按上次從佇列中獲取任務的時間對它們進行排序（佇列中等待時間最長的任務首先出現，然后是第二長的任務） - 等待佇列等）
之后，我們可以檢查已排序tasksArray的任務，并且對于我們將其分配給執行程式的每個任務（我們在開始時選擇了一個），執行程式被占用，我們將其放回執行程式堆中并更新時間記錄，這表明時刻它是免費的。然后對于 的每個下一個元素，tasksArray我們從堆中獲取一個 executor 并將任務分配給它，直到tasksArray為空。這樣的迭代是 O(N logN)。到目前為止，解決方案是 O(N N logN)。
在將所有任務tasksArray分配給它們的執行者之后，我們從佇列的前面獲取下一批任務，一切都將再次進行。這種情況一直持續到所有佇列都為空。
這個解決方案可以被認為是 O(N*logN)，但是這個解決方案是不正確的。
讓我們回到執行者已經準備好但還沒有任務的情況。在這種情況下，它會等到一個或多個佇列中的第一個任務同時出現并選擇其中一個。但是在它等待的時候，其他執行者可能會完成他們的任務并準備好。其中一些執行者的數量可能比我們選擇的要少。所以，問題來了，因為在這種情況下，我們必須選擇數字最小的那個，但是我的解決方案沒有這樣做。
這是有原因的。如果我們將 executors 存盤在堆中，那么我們就無法知道在等待時哪些 executors 已經準備好。為了確定這一點，我們需要檢查堆中的每個執行程式，并將其“就緒時間”與當前時間進行比較。然而，這樣的檢查給了我們 O(N) 的時間（我們可以遍歷佇列的底層陣列，而不是佇列本身，因為我們無論如何都需要檢查所有任務）。在最壞的情況下，每 2 秒只有 1 個任務，它的處理時間很短，只有 1 秒，那么我們就會陷入執行者等待每個任務的情況。對于每個任務，我們將遍歷所有執行者。這種演算法是 O(N*N) = O(N^2)，由于時間限制，這是不可接受的。
這就是我卡住的地方。當我們在 O(N) 下及時等待任務時，我無法找到一種方法來確定是否有更多的執行者已經準備好。我也一直在考慮將資料結構從堆更改為其他結構，但這也沒有讓我走運。
那么有什么方法可以在 O(N^2) 時間內解決這個問題？
uj5u.com熱心網友回復：
您尚未完全指定關系的問題。例如，如果一個任務在一個執行器空閑的同時到達一個長時間沒有被挑選的空佇列，那么該任務是否被分配給執行器？還是其他一些任務被分配給那個執行者并且任務被分配給下一個執行者來釋放？
我假設它被分配給執行者，并且不會處理其他關系。但是您應該在解決方案中仔細考慮這一點。
我們需要以下堆。
free_executor所以我們可以選擇數字最小的免費執行者。nonempty_queue所以我們可以從等待時間最長的佇列中挑選。- 事件。事件具有時間、型別和資訊。型別為
TaskArrival和ExecutorFinished。順序是時間，然后鍵入（TaskArrival第一個）。
現在有了這個，這就是邏輯。
while events has stuff:
event = next event
if event.type = TaskArrival:
if its queue was empty:
add its queue to nonempty_queue
add task to its queue
else:
add newly freed executor to free_executor
if free_executor and nonempty_queue both have something:
executor = free_executor.pop()
queue = nonempty_queue.pop()
task = queue.pop()
mark that executor did task
add new event to events queue for executor coming free after task is done
if queue is not empty:
put queue back into nonempty_queue with new priority
我們將為每個任務生成 2 個事件。回圈內的每個操作都需要O(1)（例如mark that executor did task）或O(log(n))（例如queue = nonempty_queue.pop()）。每個事件有固定數量的操作。因此演算法及時運行O(n log(n))。
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/517807.html
標籤：算法排序队列时间复杂度堆