title: Hackerrank's Minimum Average Waiting Time
body: <p>Link to challenge can be found <a href="https://www.hackerrank.com/challenges/minimum-average-waiting-time" rel="nofollow"><strong>here</strong></a></p>
  
  <blockquote>
    <p><strong>Problem Statement</strong></p>
    
    <p>Tieu owns a pizza restaurant and he manages it in his own way. While
    in a normal restaurant, a customer is served by following the
    first-come, first-served rule, Tieu simply minimizes the average
    waiting time of his customers. So he gets to decide who is served
    first, regardless of how sooner or later a person comes.</p>
    
    <p>Different kinds of pizzas take different amounts of time to cook.
    Also, once he starts cooking a pizza, he cannot cook another pizza
    until the first pizza is completely cooked. Let's say we have three
    customers who come at time t=0, t=1, &amp; t=2 respectively, and the time
    needed to cook their pizzas is 3, 9, &amp; 6 respectively. If Tieu applies
    first-come, first-served rule, then the waiting time of three
    customers is 3, 11, &amp; 16 respectively. The average waiting time in
    this case is (3 + 11 + 16) / 3 = 10. This is not an optimized
    solution. After serving the first customer at time t=3, Tieu can
    choose to serve the third customer. In that case, the waiting time
    will be 3, 7, &amp; 17 respectively. Hence the average waiting time is (3
    + 7 + 17) / 3 = 9.</p>
    
    <p>Help Tieu achieve the minimum average waiting time. For the sake of
    simplicity, just find the integer part of the minimum average waiting
    time.</p>
    
    <p><strong>Input Format</strong></p>
    
    <p>The first line contains an integer N, which is the number of
    customers. In the next N lines, the ith line contains two space
    separated numbers Ti and Li. Ti is the time when ith customer order a
    pizza, and Li is the time required to cook that pizza. Output Format</p>
    
    <p>Display the integer part of the minimum average waiting time.</p>
    
    <p><strong>Constraints</strong></p>
    
    <p>1 ≤ N ≤ 10^5 </p>
    
    <p>0 ≤ Ti ≤ 10^9</p>
    
    <p>1 ≤ Li ≤ 10^9 </p>
    
    <p><strong>Note</strong></p>
    
    <p>The waiting time is calculated as the difference between the time a
    customer orders pizza (the time at which they enter the shop) and the
    time she is served.</p>
    
    <p>Cook does not know about the future orders.</p>
  </blockquote>
  
  <p>I've been at this for several hours. </p>
  
  <p>I'm pretty sure my problems has to do with the way I increment the total Wait time. </p>
  
  <p>Any help would be much appreciated.</p>
  
  <p>code:</p>
  
  <pre><code>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-- &gt; 0) mawt.insert(s.nextLong(), s.nextLong());
          System.out.print(mawt.calculateAverageWaitingTime());
      }
  }
  
  class MinimumAverageWaitingTime {
      private PriorityQueue&lt;e_time_p_time&gt; incomingOrders = new PriorityQueue&lt;&gt;(10, new Comparator&lt;e_time_p_time&gt;(){
          //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&lt;e_time_p_time&gt; awaitingOrders = new PriorityQueue&lt;&gt;(10, new Comparator&lt;e_time_p_time&gt;(){
          //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() &gt; 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 &gt;= laterOrders.entryTime &amp;&amp; incomingOrders.size() &gt; 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() &gt; 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;
          }
  
      }
  }
  </code></pre>