等待名單的時間計算

Question

想象我跟在隊列

Service 1 - 5 minutes 
Service 2 - 10 minutes 
Service 3 - 5 minutes 
Service 4 - 15 minutes 
Service 5 - 20 minutes 

下一個等待名單。如果我有兩個工作人員在排隊我怎麼能估計等待時間下一個人服務這5個客戶走在商店裏。

Answer 1

其實這很簡單 - 這是"W" queue model as described by Eric Lippert。

設置陣列中兩個「工作人員」的成員：

List<int>[] staff = new [] {new List<int>(), new List<int>()}; 

定義隊列：

int[] queue = new int[] {5, 10, 5, 15, 20}; 

然後模擬處理 - 每個客戶以後會去到首先完成的服務商：

foreach (int i in queue) 
{ 
    List<int> shortest = staff.OrderBy(s=>s.Sum()).First(); 
    shortest.Add(i); 
} 

要進來的「下一個」人員必須等到第一個服務人員免費，這是每一個客戶的總和服：

int nextTime = staff.Min(s=>s.Sum()); 

Console.WriteLine("The wait time for the next customer is {0} minutes",nextTime); 

輸出：

等待時間爲下一位顧客是25分鐘。

Answer 2

這裏有一個不那麼優雅的方式來做到這一點...

private static int GetEstimatedWaitTime(Queue<int> currentQueue, int numServers) 
{ 
    int waitTime = 0; 

    // Short-circuit if there are more servers than items in the queue 
    if (currentQueue.Count < numServers) return waitTime; 

    // Create a copy of the queue so we can dequeue from it 
    var remainingItems = new Queue<int>(); 
    foreach (var item in currentQueue) 
    { 
     remainingItems.Enqueue(item); 
    } 

    // Grab an item for each server 
    var itemsBeingServiced = new List<int>(); 
    for (int i = 0; i < numServers; i++) 
    { 
     itemsBeingServiced.Add(remainingItems.Dequeue()); 
    } 

    do 
    { 
     // Get the shortest item left, increment our wait time, and adjust other items 
     itemsBeingServiced.Sort(); 
     var shortestItem = itemsBeingServiced.First(); 
     waitTime += shortestItem; 

     itemsBeingServiced.RemoveAll(item => item == shortestItem); 

     for (int i = 0; i < itemsBeingServiced.Count; i++) 
     { 
      itemsBeingServiced[i] = itemsBeingServiced[i] - shortestItem; 
     } 

     // Add more items for available servers if there are any 
     while (itemsBeingServiced.Count < numServers && remainingItems.Any()) 
     { 
      itemsBeingServiced.Add(remainingItems.Dequeue()); 
     } 

    } while (itemsBeingServiced.Count >= numServers); 

    return waitTime; 
}