Average Waiting Time

Problem Statement

In the scenario described, a restaurant operates with a single chef who is responsible for preparing food orders sequentially. The restaurant tracks customers using an array, where each element, indexed by i, is structured as customers[i] = [arrivali, timei]:

• arrivali represents the time a customer arrives at the restaurant.
• timei is the amount of time the chef requires to prepare that customer's order.

The chef can only begin preparing a new order when the previous one is complete and cannot handle more than one order simultaneously. The task is to calculate the average waiting time for all the customers. The average waiting time for a customer is calculated from the time they arrive to the time their order is complete.

The instructions specify to return the average waiting time across all customers and indicate that an accuracy within 10-5 of the actual average is acceptable for solutions, accommodating slight precision deviations in computations.

Examples

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 <= 105
• 1 <= arrivali, timei <= 104
• arrivali <= arrivali+1

Approach and Intuition

The key steps to solve this problem involve tracking the chef's service progress and the waiting times for individual customers:

1. Initialize Variables: Start with a timeline (such as current_time) initialized at zero to track when the chef can begin or finish a customer's order.

2. Iterate Over Customers: Go through each customer and take into account their arrival and the necessary preparation time.

3. Preparation Start Time: Determine when the chef can start preparing an order:

   • If the chef is idle (or the restaurant just opened), preparation begins at arrivali.
   • If the chef is busy with a previous order, preparation begins when he becomes available.

4. Calculate Waiting Time: For each customer:

   • Compute when their food preparation would be complete (current_time + timei).
   • Track the total waiting time from arrival to the completion of their order.
   • Update current_time to reflect when the chef will be free next.

5. Average the Wait Times: Once all orders have been processed, sum the waiting times for all customers and divide by the total number of customers. This results in the average waiting time.

Given the constraints, be mindful of efficiency. Processing each customer's order within this simple loop ensures an O(n) solution to tally up the average wait time.

Solutions

class Solution {
public:
    double calculateAverageWaitTime(vector<vector<int>>& customerData) {
        int chefIdleTime = 0;
        long long totalWaitTime = 0;
    
        for (int idx = 0; idx < customerData.size(); idx++) {
            chefIdleTime = max(customerData[idx][0], chefIdleTime) + customerData[idx][1];
            totalWaitTime += chefIdleTime - customerData[idx][0];
        }
    
        double avgWaitTime = static_cast<double>(totalWaitTime) / customerData.size();
        return avgWaitTime;
    }
};