# Average Waiting Time
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/average-waiting-time)
Canonical: https://scaleengineer.com/dsa/problems/average-waiting-time
**Data structures:** Array
**Companies:** [DE Shaw](https://scaleengineer.com/companies/de-shaw), [Instacart](https://scaleengineer.com/companies/instacart)
---
## Problem
There is a restaurant with a single chef. You are given an array `customers`, where `customers[i] = [arrivali, timei]:`

* `arrivali` is the arrival time of the `ith` customer. The arrival times are sorted in **non-decreasing** order.
* `timei` is the time needed to prepare the order of the `ith` 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 <= 105`
* `1 <= arrivali, timei <= 104`
* `arrivali <= arrivali+1`

# Approaches
## Simulation with Auxiliary Arrays
This approach simulates the process step-by-step for each customer. It uses additional arrays to store the start time, finish time, and waiting time for every customer. After calculating these values for all customers in a first pass, a second pass is made to sum up the waiting times and compute the average.
**Time:** O(N), where N is the number of customers. The process involves two separate loops that each run N times (one to calculate times, one to sum them). O(N) + O(N) simplifies to O(N). · **Space:** O(N), where N is the number of customers. We use three auxiliary arrays, each of size N, to store the start, finish, and waiting times.
**Pros:** The logic is straightforward and easy to trace, as all intermediate states are stored.; Storing all times can be useful for debugging or if further analysis on individual customer times were required.
**Cons:** Uses O(N) extra space, which is unnecessary as the intermediate times for previous customers are not needed to process subsequent ones.; Requires two separate passes over data of size N, making it slightly less performant than a single-pass solution.
### Explanation
In this method, we explicitly track the timeline for each customer. We maintain a variable `currentTime` to know when the chef is free. For each customer, we determine their order's start time by taking the maximum of their arrival time and the chef's `currentTime`. From this, we can calculate the finish time and, consequently, the waiting time (`finishTime - arrivalTime`).

Instead of just keeping a running total, we store these calculated `startTime`, `finishTime`, and `waitingTime` values in separate arrays. After processing all customers and populating these arrays, we perform a second iteration specifically over the `waitingTimes` array to compute the total sum. This sum is then divided by the number of customers to find the average. Using `long` for time variables is crucial to prevent integer overflow.

```java
class Solution {
    public double averageWaitingTime(int[][] customers) {
        int n = customers.length;
        long[] startTimes = new long[n];
        long[] finishTimes = new long[n];
        long[] waitingTimes = new long[n];
        
        long currentTime = 0;
        
        for (int i = 0; i < n; i++) {
            int arrival = customers[i][0];
            int time = customers[i][1];
            
            long startTime = Math.max(arrival, currentTime);
            startTimes[i] = startTime;
            
            long finishTime = startTime + time;
            finishTimes[i] = finishTime;
            
            long waitingTime = finishTime - arrival;
            waitingTimes[i] = waitingTime;
            
            currentTime = finishTime;
        }
        
        long totalWaitingTime = 0;
        for (long wt : waitingTimes) {
            totalWaitingTime += wt;
        }
        
        return (double) totalWaitingTime / n;
    }
}
```
### Algorithm
- Get the number of customers, `n`.
- Initialize three arrays of size `n`: `startTimes`, `finishTimes`, `waitingTimes` to store intermediate calculations.
- Initialize a `long` variable `currentTime = 0` to track when the chef becomes free.
- Loop through each customer `i` from `0` to `n-1`:
  - Get `arrival` and `time` for the current customer.
  - The chef starts cooking at `startTime = Math.max(arrival, currentTime)`.
  - The order is finished at `finishTime = startTime + time`.
  - The customer's waiting time is `waitingTime = finishTime - arrival`.
  - Store these three values in their respective arrays.
  - Update `currentTime = finishTime` for the next customer.
- After the first loop, initialize `totalWaitingTime = 0L`.
- Loop through the `waitingTimes` array and sum all values into `totalWaitingTime`.
- Finally, return the average by dividing `totalWaitingTime` by `n`.

## Optimized Single-Pass Simulation
This is the most efficient approach. It simulates the process in a single pass through the customer list. Instead of storing all intermediate times in arrays, it maintains a running total of the waiting time and updates the chef's availability time (`currentTime`) on the fly. This avoids the need for extra space proportional to the number of customers.
**Time:** O(N), where N is the number of customers. We perform a single pass through the input array, with constant time operations inside the loop. · **Space:** O(1). We only use a few variables (`totalWaitingTime`, `currentTime`, `n`) to store the state, which does not depend on the number of customers.
**Pros:** Extremely efficient, solving the problem in a single pass over the input data.; Optimal space complexity, as it uses only a constant amount of extra memory regardless of the input size.
**Cons:** This approach does not retain the individual waiting times for each customer, which could be a limitation if that data were needed for other purposes.
### Explanation
The core logic is to simulate the chef's work process efficiently. We only need two variables to track the state: `currentTime` (when the chef becomes free) and `totalWaitingTime` (the cumulative waiting time of all customers served so far). We initialize both to zero, using the `long` data type to handle potentially large time values and prevent overflow.

We then iterate through the `customers` array just once. For each customer, we calculate when their food preparation can start, which is the maximum of their arrival time and the chef's current free time. We then calculate the finish time and add the resulting waiting time to our `totalWaitingTime`. The crucial optimization is that we immediately update the chef's `currentTime` to this new finish time and discard the individual times, as they are no longer needed. After the loop, we simply divide the `totalWaitingTime` by the number of customers to get the average.

```java
class Solution {
    public double averageWaitingTime(int[][] customers) {
        long totalWaitingTime = 0;
        long currentTime = 0;
        int n = customers.length;
        
        for (int[] customer : customers) {
            int arrival = customer[0];
            int time = customer[1];
            
            // The chef starts at the max of their current free time and customer arrival time.
            currentTime = Math.max(arrival, currentTime);
            
            // The order is finished at the start time + preparation time.
            long finishTime = currentTime + time;
            
            // Waiting time is the difference between finish time and arrival time.
            totalWaitingTime += (finishTime - arrival);
            
            // The chef is now busy until the finish time.
            currentTime = finishTime;
        }
        
        return (double) totalWaitingTime / n;
    }
}
```
### Algorithm
- Initialize `totalWaitingTime = 0L` and `currentTime = 0L`. Using `long` prevents potential overflow.
- Get the total number of customers, `n`.
- Iterate through each `customer` in the `customers` array:
  - Get the customer's `arrival` and preparation `time`.
  - Determine when the chef can start cooking. This will be the later of the customer's arrival or the chef's current free time: `currentTime = Math.max(arrival, currentTime)`.
  - The chef will finish this order at `currentTime + time`. The waiting time is this finish time minus the arrival time.
  - Add this waiting time to the running total: `totalWaitingTime += (currentTime + time - arrival)`.
  - Update the chef's free time for the next customer. The chef is now busy until the current order is finished: `currentTime += time`.
- After the loop, calculate and return the average: `(double) totalWaitingTime / n`.

# Solutions
### Java

```java
class Solution {
public
  double averageWaitingTime(int[][] customers) {
    double tot = 0;
    int t = 0;
    for (var e : customers) {
      int a = e[0], b = e[1];
      t = Math.max(t, a) + b;
      tot += t - a;
    }
    return tot / customers.length;
  }
}

```

### JavaScript

```javascript
function averageWaitingTime ( customers ) { let [ tot , t ] = [ 0 , 0 ]; for ( const [ a , b ] of customers ) { t = Math . max ( t , a ) + b ; tot += t - a ; } return tot / customers . length ; }
```

### Python

```python
class Solution:
    def averageWaitingTime(self, customers: List[List[int]]) -> float: tot = t = 0 for a, b in customers: t = max(t, a) + b tot += t - a return tot / len(customers)

```

### CPP

```cpp
class Solution {
public:
  double averageWaitingTime(vector<vector<int>> &customers) {
    double tot = 0;
    int t = 0;
    for (auto &e : customers) {
      int a = e[0], b = e[1];
      t = max(t, a) + b;
      tot += t - a;
    }
    return tot / customers.size();
  }
};

```