java - Hackerrank 的最小平均等待时间

Question

可以找到挑战链接 here

Problem Statement

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.

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, & t=2 respectively, and the time needed to cook their pizzas is 3, 9, & 6 respectively. If Tieu applies first-come, first-served rule, then the waiting time of three customers is 3, 11, & 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, & 17 respectively. Hence the average waiting time is (3 + 7 + 17) / 3 = 9.

Help Tieu achieve the minimum average waiting time. For the sake of simplicity, just find the integer part of the minimum average waiting time.

Input Format

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

Display the integer part of the minimum average waiting time.

Constraints

1 ≤ N ≤ 10^5

0 ≤ Ti ≤ 10^9

1 ≤ Li ≤ 10^9

Note

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.

Cook does not know about the future orders.

我已经处理了好几个小时了。

我很确定我的问题与增加总等待时间的方式有关。

如有任何帮助，我们将不胜感激。

代码:

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. 您始终至少向 waitingOrders 添加一项 - 但如果当前比萨饼还在 toastr 中时没有人进入商店怎么办？ (例如最后一个披萨)
2. 您比较 pizzaCookTime - 例如十分钟，带有 entryTime，例如下午4点。这似乎不对 - 你不应该将披萨完成的时间与 entryTime 进行比较吗？