Average Waiting Time

How it works

This is a more concise version of the simulation. The key observation is that the chef starts cooking at whichever is later: their current finish time or the customer's arrival. The finish time becomes max(t, arrival) + order. The customer's waiting time is simply finish_time - arrival. This formula captures both cases (chef idle or busy) in one expression.

Steps

1. Initialize t (finish time) and total to 0.
2. For each customer:
   • Update t to max(t, arrival) + order (when the order finishes).
   • Add t - arrival to total (customer's wait time).
3. Return total divided by the number of customers.

Complexity

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

Things to watch for

Integer Overflow

With large arrival times and order durations, the sum of waiting times can exceed 32-bit integer limits. Use 64-bit integers for accumulating totals.

Confusing Waiting Time with Service Time

Waiting time is from arrival until the order is complete (includes cooking time), not just the time spent waiting before cooking starts.

Forgetting to Update Current Time

When a customer arrives after the chef is idle, the current time must jump forward to the arrival time, not stay at the previous finish time.

from typing import List

class Solution:
    def averageWaitingTime(self, customers: List[List[int]]) -> float:
        t = total = 0
        for arrival, order in customers:
            t = max(t, arrival) + order
            total += t - arrival
        return total / len(customers)

class Solution {
public:
    double averageWaitingTime(vector<vector<int>>& customers) {
        long long t = 0, total = 0;

        for (auto& c : customers) {
            int arrival = c[0], order = c[1];
            t = max(t, (long long)arrival) + order;
            total += t - arrival;
        }

        return (double) total / customers.size();
    }
};