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吗？