Average Waiting Time

medium array simulation greedy

Problem

A restaurant has a single chef. You are given customers, where customers[i] = [arrival, time]: the i-th customer arrives at arrival (arrivals are non-decreasing) and their order needs time to prepare. The chef serves customers strictly in input order, one at a time, starting each order as soon as he is idle and the customer has arrived. A customer waits from arrival until their order is finished. Return the average waiting time over all customers.

Inputcustomers = [[1,2],[2,5],[4,3]]

Output5.00000

Waits are 2, 6, 7. Average = (2 + 6 + 7) / 3 = 5.

customers (arrival:time, comma-separated)

def average_waiting_time(customers):
    cur = 0          # time the chef becomes idle
    total = 0        # sum of all waiting times
    for arrival, time in customers:
        start = max(cur, arrival)
        finish = start + time
        total += finish - arrival
        cur = finish
    return total / len(customers)

function averageWaitingTime(customers) {
  let cur = 0;            // time the chef becomes idle
  let total = 0;         // sum of all waiting times
  for (const [arrival, time] of customers) {
    const start = Math.max(cur, arrival);
    const finish = start + time;
    total += finish - arrival;
    cur = finish;
  }
  return total / customers.length;
}

double averageWaitingTime(int[][] customers) {
    long cur = 0;          // time the chef becomes idle
    long total = 0;        // sum of all waiting times
    for (int[] c : customers) {
        long start = Math.max(cur, c[0]);
        long finish = start + c[1];
        total += finish - c[0];
        cur = finish;
    }
    return (double) total / customers.length;
}

double averageWaitingTime(vector<vector<int>>& customers) {
    long long cur = 0;     // time the chef becomes idle
    long long total = 0;   // sum of all waiting times
    for (auto& c : customers) {
        long long start = max(cur, (long long) c[0]);
        long long finish = start + c[1];
        total += finish - c[0];
        cur = finish;
    }
    return (double) total / customers.size();
}

Explanation

Because the chef serves customers strictly in input order and never works on two orders at once, the whole process is a clean left-to-right simulation. We only need one running value: cur, the moment the chef next becomes free.

For each customer [arrival, time] the chef can only begin once both conditions hold: the customer has arrived and the chef is idle. That start time is therefore start = max(cur, arrival). If the chef is still busy (cur > arrival) the customer waits in line; if the chef is already idle (cur ≤ arrival) cooking begins right at arrival.

The order finishes at finish = start + time, and this customer's waiting time — from when they arrived until their food is ready — is finish - arrival. We add that into total and advance the chef's clock with cur = finish so the next customer sees the updated free time.

After one pass we divide total by the number of customers to get the average. A single linear scan with O(1) extra state makes this O(n) time and O(1) space.

Example: [[1,2],[2,5],[4,3]]. Customer 1 cooks 1→3 (wait 2). Customer 2 cooks 3→8 (wait 6). Customer 3 cooks 8→11 (wait 7). Average = (2 + 6 + 7) / 3 = 5.

Time: O(n) Space: O(1)