首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >问答首页 >Hackerrank最小平均等待时间

Hackerrank最小平均等待时间
EN

Stack Overflow用户
提问于 2015-07-03 19:55:08
回答 1查看 5.9K关注 0票数 3

指向挑战的链接可以找到here

问题陈述 Tieu拥有一家比萨饼店,他以自己的方式经营。在一家普通的餐馆里,顾客是按照先到先得的原则来服务的,而Tieu只是将顾客的平均等候时间降到最低。所以他可以决定谁先被服务,不管一个人迟早会来。 不同种类的比萨饼需要不同的时间烹饪。而且,一旦他开始做比萨饼,他就不能再做一个比萨饼,直到第一个比萨饼完全煮熟。假设我们有三个顾客,分别是t=0,t=1,& t=2,他们做比萨饼所需的时间分别是3、9和6。如果Tieu采用先到先得的规则,那么三个顾客的等待时间分别为3、11和16。这种情况下的平均等待时间是(3 + 11 + 16) /3= 10。这不是一个优化的解决方案。在时间t=3为第一位客户服务之后,Tieu可以选择为第三位客户服务。在此情况下,轮候时间分别为3、7及17。因此,平均等待时间为(3 +7+ 17) /3= 9。 帮助Tieu达到最低平均等待时间。为了简单起见,只需找到最小平均等待时间的整数部分即可。 输入格式 第一行包含一个整数N,即客户数。在接下来的N条线中,第1条线包含两个分隔的数字Ti和Li。时间是你的顾客点披萨的时候,而李是煮披萨所需要的时间。输出格式 显示最小平均等待时间的整数部分。 约束 1≤N≤10^5 0≤Ti≤10^9 1≤Li≤10^9 Note 等待时间计算为顾客订购比萨饼的时间(他们进入商店的时间)和服务时间之间的差异。 库克不知道未来的订单。

我已经干了好几个小时了。

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

任何帮助都将不胜感激。

代码:

代码语言:javascript
运行
复制
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;
        }

    }
}
EN

回答 1

Stack Overflow用户

发布于 2015-07-03 20:07:29

在此代码中:

代码语言:javascript
运行
复制
     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 -例如10分钟,与entryTime比较,例如下午4点这似乎不对--难道你不应该把比萨饼完成的时间和entryTime进行比较吗?
票数 2
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/31213473

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档