We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Data Structures
  3. Heap
  4. Minimum Average Waiting Time
  5. Discussions

Minimum Average Waiting Time

Sort by

recency

|

182 Discussions

|

  • Praveendsinha
     + 0 comments

    Yeah I feel the same changing the return value of function to long makes it work, How and where to log bug for correction of this.

  • christian_maech1
     + 0 comments

    Change return value of function to long in Java to make it work.

  • macohip968
     + 0 comments

    Great problem! Reminds me of how Jun blades — razor-sharp and precise — can make all the difference in a kitchen. Just like Tieu optimizing wait times, the right tool (or algorithm!) cuts through inefficiency. Here, a min-heap for shortest cook time works like a Jun blade — sleek and effective.

  • manceraaxel
     + 0 comments
    import heapq

def minimumAverage(customers):
    customers.sort()
    n = len(customers)
    i = 0
    current_time = 0
    waiting_time = 0
    h = []

    while i < n or h:
        # Add all custoemrs with arrival time less or equal to current time so that no customer that arrives later is processed, as that is not valid.
        while i < n and customers[i][0] <= current_time:
            heapq.heappush(h, (customers[i][1], customers[i][0]))
            i += 1

        # From the clients whose arrival time is less than the current time, extract the one whose pizza has the least preparation time.
        if h:
            prep_time, arrival_time = heapq.heappop(h)
            current_time += prep_time
            waiting_time += current_time - arrival_time

        # In case there are no customers to process, move to next customer. :)
        else:
            current_time = customers[i][0]

    return waiting_time // n

  • phongthuypts
     + 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();
}