Average Waiting Time

Medium

Instacart

3 views

Topics:

Arrays

There is a restaurant with a single chef. You are given an array customers, where customers[i] = [arrival_i, time_i]:

arrival_i is the arrival time of the i^th customer. The arrival times are sorted in non-decreasing order.
time_i is the time needed to prepare the order of the i^th customer.

When a customer arrives, he gives the chef his order, and the chef starts preparing it once he is idle. The customer waits till the chef finishes preparing his order. The chef does not prepare food for more than one customer at a time. The chef prepares food for customers in the order they were given in the input.

Return the average waiting time of all customers. Solutions within 10^-5 from the actual answer are considered accepted.

Example 1:

Input: customers = [[1,2],[2,5],[4,3]]
Output: 5.00000
Explanation:
1) The first customer arrives at time 1, the chef takes his order and starts preparing it immediately at time 1, and finishes at time 3, so the waiting time of the first customer is 3 - 1 = 2.
2) The second customer arrives at time 2, the chef takes his order and starts preparing it at time 3, and finishes at time 8, so the waiting time of the second customer is 8 - 2 = 6.
3) The third customer arrives at time 4, the chef takes his order and starts preparing it at time 8, and finishes at time 11, so the waiting time of the third customer is 11 - 4 = 7.
So the average waiting time = (2 + 6 + 7) / 3 = 5.

Example 2:

Input: customers = [[5,2],[5,4],[10,3],[20,1]]
Output: 3.25000
Explanation:
1) The first customer arrives at time 5, the chef takes his order and starts preparing it immediately at time 5, and finishes at time 7, so the waiting time of the first customer is 7 - 5 = 2.
2) The second customer arrives at time 5, the chef takes his order and starts preparing it at time 7, and finishes at time 11, so the waiting time of the second customer is 11 - 5 = 6.
3) The third customer arrives at time 10, the chef takes his order and starts preparing it at time 11, and finishes at time 14, so the waiting time of the third customer is 14 - 10 = 4.
4) The fourth customer arrives at time 20, the chef takes his order and starts preparing it immediately at time 20, and finishes at time 21, so the waiting time of the fourth customer is 21 - 20 = 1.
So the average waiting time = (2 + 6 + 4 + 1) / 4 = 3.25.

Constraints:

1 <= customers.length <= 10⁵
1 <= arrival_i, time_i <= 10⁴
arrival_i<= arrival_i+1

Average Waiting Time

Medium

Instacart

3 views

Topics:

Arrays

There is a restaurant with a single chef. You are given an array customers, where customers[i] = [arrival_i, time_i]:

arrival_i is the arrival time of the i^th customer. The arrival times are sorted in non-decreasing order.
time_i is the time needed to prepare the order of the i^th customer.

When a customer arrives, he gives the chef his order, and the chef starts preparing it once he is idle. The customer waits till the chef finishes preparing his order. The chef does not prepare food for more than one customer at a time. The chef prepares food for customers in the order they were given in the input.

Return the average waiting time of all customers. Solutions within 10^-5 from the actual answer are considered accepted.

Example 1:

Input: customers = [[1,2],[2,5],[4,3]]
Output: 5.00000
Explanation:
1) The first customer arrives at time 1, the chef takes his order and starts preparing it immediately at time 1, and finishes at time 3, so the waiting time of the first customer is 3 - 1 = 2.
2) The second customer arrives at time 2, the chef takes his order and starts preparing it at time 3, and finishes at time 8, so the waiting time of the second customer is 8 - 2 = 6.
3) The third customer arrives at time 4, the chef takes his order and starts preparing it at time 8, and finishes at time 11, so the waiting time of the third customer is 11 - 4 = 7.
So the average waiting time = (2 + 6 + 7) / 3 = 5.

Example 2:

Input: customers = [[5,2],[5,4],[10,3],[20,1]]
Output: 3.25000
Explanation:
1) The first customer arrives at time 5, the chef takes his order and starts preparing it immediately at time 5, and finishes at time 7, so the waiting time of the first customer is 7 - 5 = 2.
2) The second customer arrives at time 5, the chef takes his order and starts preparing it at time 7, and finishes at time 11, so the waiting time of the second customer is 11 - 5 = 6.
3) The third customer arrives at time 10, the chef takes his order and starts preparing it at time 11, and finishes at time 14, so the waiting time of the third customer is 14 - 10 = 4.
4) The fourth customer arrives at time 20, the chef takes his order and starts preparing it immediately at time 20, and finishes at time 21, so the waiting time of the fourth customer is 21 - 20 = 1.
So the average waiting time = (2 + 6 + 4 + 1) / 4 = 3.25.

Constraints:

1 <= customers.length <= 10⁵
1 <= arrival_i, time_i <= 10⁴
arrival_i<= arrival_i+1

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the arrival time and service time? Can they be zero or negative?
Is the input array guaranteed to be sorted by arrival time, or do I need to sort it first?
If a customer arrives at the exact time another customer finishes being served, should the new customer be served immediately, or must they wait?
If the input array is empty, what should the return value be? Should I return 0 or throw an exception?
What data type should I use to represent the average waiting time? Should I round to the nearest integer, or maintain floating-point precision?

Brute Force Solution

Approach

To calculate the average waiting time the brute force way, we consider all possible orders in which to serve the customers. We then calculate the waiting time for each ordering and find the average of those waiting times.

Here's how the algorithm would work step-by-step:

First, list every single possible order to serve the customers. This means trying every arrangement of the customers.
For each of these orderings, calculate the waiting time for each customer.
To calculate a customer's waiting time, you need to know when they arrived and when their order was finished. The waiting time is the difference between these two.
Add up all the waiting times for that particular customer ordering.
Once you've added up the total waiting time for each possible customer ordering, find the average of those total waiting times.
This average will be the brute force solution for the average waiting time.

Code Implementation

import itertools

def average_waiting_time_brute_force(customers):
    all_possible_orderings = list(itertools.permutations(customers))
    total_waiting_times = 0

    for customer_ordering in all_possible_orderings:
        current_time = 0
        total_waiting_time_for_ordering = 0

        for arrival_time, service_time in customer_ordering:
            # Calculate the finish time for the current customer
            current_time = max(current_time, arrival_time) + service_time

            waiting_time = current_time - arrival_time
            total_waiting_time_for_ordering += waiting_time

        total_waiting_times += total_waiting_time_for_ordering

    # Calculating the average waiting time
    average_waiting_time = total_waiting_times / len(all_possible_orderings)
    return average_waiting_time

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n! * n) – The algorithm begins by generating all possible orderings (permutations) of the n customers. Generating all permutations takes O(n!) time. For each permutation, the algorithm iterates through the customers to calculate the waiting time for each customer in that specific ordering. This iteration takes O(n) time. Since this calculation is performed for every permutation, the overall time complexity is O(n! * n).

Space Complexity

O(N!) – The brute force approach generates all possible orderings of customers. Generating all permutations of N customers requires storing these permutations, which results in the storage of N! orderings. Each ordering consists of N customer arrival and serving times. Thus, space is required to store the permutations, and the space complexity grows factorially with the number of customers, N. This leads to a space complexity of O(N!).

Optimal Solution

Approach

The key to minimizing average waiting time is to process customers in the order that minimizes their impact on the total wait. Specifically, we want to serve shorter jobs before longer ones, because each job increases the waiting time of all jobs that come after it. We can't just serve them in the order given, we need to reorder them optimally.

Here's how the algorithm would work step-by-step:

First, arrange the customers based on how long their service takes, from shortest to longest. If two customers take the same amount of time, their order doesn't matter.
Keep track of the current time, starting at zero.
Start serving the first customer in the sorted list. Their waiting time is simply the current time.
Add the first customer's service time to the current time. This represents the moment the first customer is done.
The next customer's waiting time is the current time, because that's how long they had to wait. Add this waiting time to your total.
Add the second customer's service time to the current time, updating the time for when they are finished.
Repeat this process for all customers, always adding their waiting time to the total and updating the current time.
Once you've processed all customers, divide the total waiting time by the number of customers. This gives you the average waiting time.

Code Implementation

def calculate_average_waiting_time(customers):
    customers.sort(key=lambda x: x[0])

    current_time = 0
    total_waiting_time = 0

    # Iterate through the sorted customers to calculate waiting times.
    for arrival_time, service_time in customers:

        if current_time <= arrival_time:
            current_time = arrival_time

        # Each customer's wait time is the current time minus arrival time.
        waiting_time = current_time - arrival_time
        total_waiting_time += waiting_time

        # Current time becomes the time when current customer finishes.
        current_time += service_time

    # Calculates the average waiting time by dividing by num of customers.
    average_waiting_time = total_waiting_time / len(customers)
    return average_waiting_time

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n log n) – The dominant operation in this algorithm is sorting the customers based on their service time. Common efficient sorting algorithms, such as merge sort or quicksort, have a time complexity of O(n log n), where n is the number of customers. The rest of the operations, involving iterating through the sorted customers and calculating the waiting time, take O(n) time. Since O(n log n) grows faster than O(n) as n increases, the overall time complexity is O(n log n).

Space Complexity

O(N) – The primary space complexity comes from reordering the customers based on their service time, which implies creating a new sorted data structure. Since the number of customers is N, the sorted list will also have a size of N. The other variables like 'current time' and 'total waiting time' occupy constant space. Therefore, the auxiliary space used is proportional to N, resulting in a space complexity of O(N).

Edge Cases

Case	How to Handle
Empty list of customers.	Return 0 as there are no waiting times to average.
List of customers with identical arrival times.	Process customers in order of shortest processing time to minimize total waiting time.
List of customers where processing time is 0.	Consider them as having no service time, so they leave immediately upon arrival.
List of customers with extremely large processing times.	Use long data type to avoid integer overflow when calculating completion and waiting times.
Large input size close to the maximum limit.	Ensure that the sorting algorithm used is efficient (e.g., O(n log n)) to avoid exceeding time limit.
Customers arrive while the chef is idle.	Set current time to the arrival time of the next customer to begin processing them immediately.
Floating-point division precision issues for the average.	Use double data type for the average waiting time and ensure sufficient precision.
All customers arrive after the last customer is served.	The waiting time for each customer is simply their processing time, as the chef is always idle when they arrive.