#1701

Medium

LeetCode Problem Workspace

Average Waiting Time

Compute the average waiting time for customers using array traversal and simulation of a single chef processing orders sequentially.

array simulation

Problem Statement

You are managing a restaurant with a single chef. Each customer arrives at a specific time and gives their order, represented as an array customers where customers[i] = [arrivali, timei]. The chef prepares each order in the order received and only works on one order at a time.

Compute and return the average waiting time of all customers. The waiting time for a customer is the time from their arrival until their order is completed. Solutions within 10^-5 of the actual answer are accepted. Ensure the simulation correctly accounts for the chef being idle or busy when each customer arrives.

Examples

Example 1

Input: customers = [[1,2],[2,5],[4,3]]

Output: 5.00000

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.
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.
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

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.
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.
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.
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

Solution Approach

Iterate with Chef Availability

Track the current time when the chef will be free. For each customer, update the start time to be the maximum of arrival time and chef availability. Calculate the waiting time as the finish time minus the arrival time, then update the chef's availability to the finish time.

Aggregate Waiting Times

Maintain a cumulative sum of all individual waiting times while iterating. After processing all customers, divide the total waiting time by the number of customers to obtain the average waiting time. This ensures precise computation even when customers overlap in arrival.

Edge Cases and Simulation Accuracy

Handle cases where customers arrive while the chef is idle versus when the chef is still busy. Ensure the simulation respects sequential order processing and correctly calculates waiting times without skipping any customer or misaligning times.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(1)

Time complexity is O(n) because we iterate through the customer array once, computing waiting times. Space complexity is O(1) since only counters and time trackers are maintained without extra arrays.

What Interviewers Usually Probe

Watch for handling customers arriving while the chef is still busy.
Ensure floating point precision is accurate for the average calculation.
Check if the simulation correctly updates chef availability after each order.

Common Pitfalls or Variants

Common pitfalls

Starting the chef's time from zero without accounting for initial customer arrival.
Incorrectly calculating waiting time by not using max(arrival, chefAvailable).
Accumulating waiting times as integers without converting to float for average.

Follow-up variants

Calculate maximum waiting time instead of average to identify peak delays.
Simulate multiple chefs processing orders concurrently while maintaining order sequence per chef.
Handle dynamic arrivals where customers may cancel or add orders during simulation.

FAQ

What is the main pattern to recognize in Average Waiting Time?

The problem follows an Array plus Simulation pattern, iterating through customer arrivals while maintaining sequential chef processing.

How do I handle customers arriving while the chef is busy?

Use max(arrivalTime, chefAvailableTime) to determine when the chef starts each order, ensuring correct waiting time calculation.

Is floating point precision important for the average?

Yes, ensure results are accurate within 10^-5 by using appropriate float or double division when computing averages.

Can this solution handle large arrays efficiently?

Yes, the algorithm runs in O(n) time and O(1) space, suitable for arrays up to 10^5 elements.

What common mistakes should I avoid in this simulation?

Avoid miscalculating start times, skipping the max(arrival, chefAvailable) logic, or using integer division when computing the average.

terminal

Solution

Solution 1: Simulation

We use a variable `tot` to record the total waiting time of the customers, and a variable `t` to record the time when each customer's order is completed. The initial values of both are $0$.

1

2

3

4

5

6

7

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)

Continue Practicing

#1700 number of students unable to eat lunch #1706 where will the ball fall #1646 get maximum in generated array