Minimum Average Waiting Time

  • + 0 comments

    This code passes all test cases

    public static long minimumAverage(List> customers) { // Write your code here // Assumption from the problem statement: // 1. The first order is always cooked first.

        customers.sort(new Comparator<List<Integer>>() {
            public int compare(List<Integer> o1, List<Integer> o2)
            {
                return o1.get(0) - o2.get(0);
            }
        });
        PriorityQueue<List<Integer>> cookQueue = new PriorityQueue<>();
        PriorityQueue<List<Integer>> orderQueue = new PriorityQueue<>(new Comparator<List<Integer>>()
        {
            public int compare(List<Integer> o1, List<Integer> o2)
            {
                return o1.get(1) - o2.get(1); // Sort based on cook time.
            }
        }); 
        long totalCookTime = 0;
        long totalWaitTime = 0;
    
        if(customers.isEmpty())
            return 0;
        // The first order is always cooked first
        cookQueue.add(customers.get(0));
        for(int i = 1; i < customers.size(); i++)
            orderQueue.add(customers.get(i));
        long firstOrderTime = cookQueue.peek().get(0);
        while(!cookQueue.isEmpty())
        {
            List<Integer> order = cookQueue.remove();
            int orderTime = order.get(0);
            int cookTime = order.get(1);
            totalCookTime += cookTime;
            totalWaitTime += (totalCookTime + firstOrderTime - orderTime);
    
            List<List<Integer>> holding = new ArrayList<>();
            while(!orderQueue.isEmpty() && orderQueue.peek().get(0) > (totalCookTime + firstOrderTime))
                holding.add(orderQueue.remove());
            if(!orderQueue.isEmpty())
                cookQueue.add(orderQueue.remove()); 
            if(!holding.isEmpty())
                orderQueue.addAll(holding); 
    
            // If there is a gap between order time and cook time (pizza oven idles)
            if(cookQueue.isEmpty() && !orderQueue.isEmpty())
            {
                cookQueue.add(orderQueue.remove());
                firstOrderTime = cookQueue.peek().get(0); //Reset the anchor point. 
                totalWaitTime = 0;
            }
        } 
        return totalWaitTime / customers.size();
    }