Average Waiting Time

Problem Description

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.

Key Insights

• The customers arrive in a non-decreasing order of arrival time.
• The chef can only serve one customer at a time.
• Waiting time for a customer is determined by when the chef starts and finishes their order.
• To compute the average waiting time, we need to track the total waiting time of all customers and divide it by the number of customers.

Space and Time Complexity

Time Complexity: O(n) - We iterate through the list of customers once. Space Complexity: O(1) - We only use a few variables to keep track of the total waiting time and the current time.

Solution

To solve this problem, we will simulate the process of customers arriving and the chef preparing their orders. We will keep track of the current time and the total waiting time as we iterate through the list of customers.

1. Initialize current_time to 0 and total_waiting_time to 0.
2. For each customer:
   • If the customer arrives after the chef is free, update current_time to the customer's arrival time.
   • Calculate the waiting time for the customer as current_time - arrival_time.
   • Add the customer's preparation time to current_time.
   • Accumulate the waiting time into total_waiting_time.
3. Finally, calculate the average by dividing total_waiting_time by the number of customers.

Code Solutions