Average Waiting Time
Medium
You are given an array customers, where customers[i] = [arrival_i, time_i] represents the arrival time and service time for the i-th customer at a restaurant with a single chef. The arrival times are sorted in non-decreasing order. The chef prepares food for customers in the order they arrive, one at a time. Return the average waiting time of all customers. Solutions within 10^-5 of the actual answer are considered correct.
For example:
customers = [[1,2],[2,5],[4,3]] Output: 5.00000
Explanation: Customer 1 arrives at time 1, is served immediately, and finishes at time 3. Waiting time: 3 - 1 = 2. Customer 2 arrives at time 2, is served starting at time 3, and finishes at time 8. Waiting time: 8 - 2 = 6. Customer 3 arrives at time 4, is served starting at time 8, and finishes at time 11. Waiting time: 11 - 4 = 7. Average waiting time = (2 + 6 + 7) / 3 = 5.
customers = [[5,2],[5,4],[10,3],[20,1]] Output: 3.25000
Explanation: Customer 1 arrives at time 5, is served immediately, and finishes at time 7. Waiting time: 7 - 5 = 2. Customer 2 arrives at time 5, is served starting at time 7, and finishes at time 11. Waiting time: 11 - 5 = 6. Customer 3 arrives at time 10, is served starting at time 11, and finishes at time 14. Waiting time: 14 - 10 = 4. Customer 4 arrives at time 20, is served immediately, and finishes at time 21. Waiting time: 21 - 20 = 1. Average waiting time = (2 + 6 + 4 + 1) / 4 = 3.25.
Constraints:
1 <= customers.length <= 10^5 1 <= arrival_i, time_i <= 10^4 arrival_i <= arrival_i+1
Solution
Naive Approach
The naive approach is to iterate through the customers array and calculate the waiting time for each customer based on the chef's availability. The chef starts preparing the first customer's order immediately upon arrival. For subsequent customers, the chef starts preparing their order either at their arrival time or when the chef finishes the previous order, whichever is later. The waiting time for each customer is the difference between the time the chef finishes their order and their arrival time. Finally, the average waiting time is the sum of all waiting times divided by the number of customers.
Big O Runtime: O(n), where n is the number of customers, due to the single loop.
Big O Space Usage: O(1), as we only use a few variables to store the total waiting time and the current time.
def average_waiting_time_naive(customers):
n = len(customers)
current_time = 0
total_waiting_time = 0
for arrival_time, service_time in customers:
current_time = max(current_time, arrival_time) + service_time
total_waiting_time += current_time - arrival_time
return total_waiting_time / n
Optimal Approach
The optimal approach is essentially the same as the naive approach because we need to process each customer in order to compute their waiting time. The key is to keep track of the current time (when the chef is available) and iterate through the customers while accumulating the waiting times.
Edge Cases:
- If the customer list is empty, return 0.
- The arrival times are sorted in non-decreasing order, so we don't need to handle unsorted arrival times.
def average_waiting_time(customers):
n = len(customers)
current_time = 0
total_waiting_time = 0
for arrival_time, service_time in customers:
current_time = max(current_time, arrival_time) + service_time
total_waiting_time += current_time - arrival_time
return total_waiting_time / n
Big O Runtime: O(n), where n is the number of customers.
Big O Space Usage: O(1), as we only use a few variables to store the total waiting time and the current time.
