Hackerrank的最小平均等待時間

Question

鏈接來挑戰，可以發現here

問題陳述

小芹擁有一家比薩餅店，他管理它自己的方式。而在一家普通餐廳的 ，顧客服務遵循先到先得的原則 ，Tieu只是最小化了他的顧客的平均等候時間。因此，無論一個人多遲或多晚來到，他都會首先決定首先向誰服務 。

不同種類的比薩需要不同的烹飪時間。另外，一旦他開始烹製比薩餅，他就不能再烹製其他比薩餅 ，直到第一批比薩餅完全熟化。假設我們有三個分別在時間t = 0，t = 1,& t = 2來到的 客戶，並且烹飪比薩餅所需的時間分別爲3,9,& 6。如果Tieu採用先到先得的原則 ，那麼三個 客戶的等待時間分別爲3,11,& 16。 這種情況下的平均等待時間是（3 + 11 + 16）/ 3 = 10。這不是一個優化的 解決方案。在時間t = 3服務第一位顧客後，鐵谷 選擇爲第三位顧客服務。在這種情況下，等待時間 將分別爲3,7,&17。因此，平均等待時間是（3 + 7 + 17）/ 3 = 9.

幫助Tieu實現最小的平均等待時間。爲了簡單起見，只需找到等待 時間的最小平均值的整數部分。

輸入格式

第一行包含一個整數N，這是 客戶的數量。在接下來的N行中，第i行包含兩個空格 分隔號碼Ti和Li。 Ti是第i個顧客訂購比薩餅的時間，而Li是烹製該比薩餅所需的時間。輸出格式

顯示最小平均等待時間的整數部分。

約束

1≤N≤10^5

0≤鈦≤10^9

1≤慄≤10^9

注

等待時間的計算方法爲時間差客戶訂單披薩（他們進入商店的時間）以及送達時間的 。

庫克不知道未來的訂單。

我已經在這幾個小時了。

我很確定我的問題與增加總等待時間的方式有關。

任何幫助將不勝感激。

代碼：

import java.io.*; 
import java.util.*; 
import java.text.*; 
import java.math.*; 

public class Solution { 

    public static void main(String[] args) { 
     Scanner s = new Scanner(System.in); 
     int n = s.nextInt(); 

     MinimumAverageWaitingTime mawt = new MinimumAverageWaitingTime(); 

     while(n-- > 0) mawt.insert(s.nextLong(), s.nextLong()); 
     System.out.print(mawt.calculateAverageWaitingTime()); 
    } 
} 

class MinimumAverageWaitingTime { 
    private PriorityQueue<e_time_p_time> incomingOrders = new PriorityQueue<>(10, new Comparator<e_time_p_time>(){ 
     //Order by the customerWaitTime ASC 
     @Override public int compare(e_time_p_time w, e_time_p_time w1) { 
      return (int) (w.entryTime - w1.entryTime); 
     } 
    }); 
    private PriorityQueue<e_time_p_time> awaitingOrders = new PriorityQueue<>(10, new Comparator<e_time_p_time>(){ 
     //Order by the difference between entrytime and pizzaCookTime ASC 
     @Override public int compare(e_time_p_time w, e_time_p_time w1) { 
      return (int) (Math.abs(w.entryTime - w.pizzaCookTime) - Math.abs(w1.entryTime - w1.pizzaCookTime)); 
     } 
    }); 

    private long total = 0l; 

    public void insert(long customerWaitTime, long pizzaCookTime) {     
     incomingOrders.add(new e_time_p_time(customerWaitTime, pizzaCookTime)); 
    } 

    public long calculateAverageWaitingTime() { 
     int size = incomingOrders.size(); 

     e_time_p_time currentOrder = null; 
     e_time_p_time laterOrders = null; 

     while(incomingOrders.size() > 0) { 
      //Start by getting the customer that has the earliest arrival time (the queue is sorted that way) 
      currentOrder = incomingOrders.remove(); 

      //Calculate it's waiting time. 
      total += currentOrder.entryTime + currentOrder.pizzaCookTime; 

      do { 
       /*Move all the customers that entered the shop while the current pizza is in the oven 
        to the awaitingOrders orders queue*/ 
       laterOrders = incomingOrders.remove(); 
       awaitingOrders.add(laterOrders); 
      } while (currentOrder.pizzaCookTime >= laterOrders.entryTime && incomingOrders.size() > 0); 

      //Go through awaitingOrders queue and calculate waiting time for the remaining orders 
      //(The queue is sorted as the difference between entrytime and pizzaCookTime ASC) 
      while(awaitingOrders.size() > 0) { 
       e_time_p_time shortestOrder = awaitingOrders.remove(); 
       long waitTimeBeforeCooking = Math.abs((shortestOrder.entryTime + shortestOrder.pizzaCookTime) - currentOrder.entryTime); 
       total += waitTimeBeforeCooking; 
      } 
     } 

     //It's supposed to be the average time, but first I need the total to be correct, and right now, it's not... 
     System.out.println("\nTotal waiting time: "); 
     return total; 
    } 

    private static class e_time_p_time { 
     private long entryTime; 
     private long pizzaCookTime; 

     e_time_p_time(long entryTime, long pizzaCookTime) { 
      this.entryTime = entryTime; 
      this.pizzaCookTime = pizzaCookTime; 
     } 

    } 
} 

Answer 1

在此代碼：

 do { 
      /*Move all the customers that entered the shop while the current pizza is in the oven 
       to the awaitingOrders orders queue*/ 
      laterOrders = incomingOrders.remove(); 
      awaitingOrders.add(laterOrders); 
     } while (currentOrder.pizzaCookTime >= laterOrders.entryTime && incomingOrders.size() > 0); 

一對夫婦的事情似乎錯在這裏：

1. 你總是至少有一個項目添加到awaitingOrders - 但什麼如果當前披薩在烤箱中沒有人進入商店？ （例如最後的披薩）
2. 您可以比較pizzaCookTime - 例如十分鐘，用entryTime，例如下午4點。這看起來不正確 - 你不應該比較披薩的完成時間和entryTime嗎？