Minimum Average Waiting Time

Discussion Video

The first, and most important, observation to note is because we are attempting to minimize the total wait time, not caring about the individual customer wait times, the goal at each moment while serving the customers is to minimize the number of people waiting (why?).

Therefore, each time we need to select the next customer to serve, we choose the one with the shortest cooking time for their order.

A priority queue is a great data structure for storing the customers. Python’s heapq data structure offers an implementation of a priority queue having $O(\log n)$ insertion and removal times (i.e. logarithmic in the number of elements currently stored in the heap).

An additional wrinkle in this problem is that the input data is not necessarily given in order of the customer arrival times, which can be gotten around simply by sorting the customer list. Note that we reverse sort, so we can pop off the list and get the next customer. We then create an instore queue to hold those customers already arrived, ordered by cooking time. Each time a pizza is finished cooking, we move any customers that arrived during the preparation of that order to instore, and then select the shortest cooking-time pizza to make. Some additional logic handles the case where the instore queue empties with customers still to arrive.

import heapq

def minimumAverage(customers):
    # key idea: always cook the fastest pizza
    # this minimizes the _average_ waiting time by getting people out of the door

    # get them time ordered, in reverse for popping reasons
    customers.sort(reverse=True)
    instore = []
    time = customers[-1][0]

    total_wait = 0
    total_cust = 0

    while customers or instore:
        # if no customers waiting and no one to arrive, advance time to next customer
        if len(instore) == 0 and customers and customers[-1][0] > time:
            time = customers[-1][0]

        # add customers that have arrived
        # note heap is by cook time, so put that first in tuple
        while customers and customers[-1][0] <= time:
            arrive, cook = customers.pop()
            heapq.heappush(instore, (cook, arrive))

        # cook the fastest, advance the time
        # also track how long that customer has been waiting
        cook, arrive = heapq.heappop(instore)
        time += cook
        total_wait += time - arrive
        total_cust += 1

    return total_wait // total_cust