LeetCode 1701 - Average Waiting Time

LeetCode Problem 1701

Difficulty: 🟡 Medium
Topics: Array, Simulation

Solution

Problem Understanding

This problem is asking us to simulate the operation of a single-chef restaurant, where customers arrive at certain times and each customer has a specific preparation time for their order. The goal is to calculate the average waiting time for all customers. The waiting time for a customer is the total time they spend in the system from arrival until their order is finished.

The input customers is a 2D array where each element [arrivali, timei] represents a single customer. arrivali is the exact time the customer arrives, and timei is the amount of time the chef needs to prepare their order. The customers are guaranteed to be sorted by arrival time in non-decreasing order. The expected output is a floating-point number representing the average waiting time across all customers. The answer must be precise within 10^-5.

Constraints tell us that the number of customers can be as large as 10^5, and the time values can go up to 10^4. This indicates that we need a linear-time solution rather than anything with nested loops over the customer list. The constraints guarantee that the arrival times are non-decreasing, so we do not have to handle sorting or out-of-order arrivals. Edge cases include customers arriving at the same time, very large preparation times, or customers arriving long after the previous order has finished.

Approaches

The brute-force approach would simulate time second by second, keeping track of when the chef is busy and when each order finishes. For each second, you would check if the chef is idle and if any customer is waiting. While this approach gives the correct answer, it is extremely inefficient, especially when arrivali can be as large as 10^4 and customers.length can be 10^5. It could take up to 10^9 steps in the worst case, which is far too slow.

The optimal approach leverages the fact that customers are already sorted by arrival time and that the chef only works on one order at a time. We maintain a single variable, current_time, representing when the chef will be free. For each customer, the chef starts preparing their order at the later of the customer's arrival time and current_time. We then compute the waiting time as the difference between the order completion time and the arrival time. This approach only requires a single pass through the customer list.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(max(arrival) * n)	O(1)	Simulate each second, check chef and customers
Optimal	O(n)	O(1)	Track chef availability and compute waiting time in one pass

Algorithm Walkthrough

1. Initialize current_time to 0. This variable represents when the chef will finish the previous order or be ready to start a new one.
2. Initialize total_waiting_time to 0. This variable accumulates the total waiting time of all customers.
3. Iterate through each customer [arrival, time] in the customers list.
4. For each customer, calculate the start time of their order as max(current_time, arrival). This ensures the chef starts as soon as possible but never before the customer arrives.
5. Compute the finish time of the order as start_time + time.
6. Calculate the waiting time as finish_time - arrival and add it to total_waiting_time.
7. Update current_time to finish_time for the next iteration.
8. After processing all customers, compute the average waiting time as total_waiting_time / number_of_customers.
9. Return the average waiting time as a floating-point number.

This algorithm works because at each step, current_time accurately represents when the chef will be free. By taking max(current_time, arrival), we ensure the chef never starts before the customer arrives. Summing all waiting times and dividing by the total number of customers guarantees the correct average.

Python Solution

from typing import List

class Solution:
    def averageWaitingTime(self, customers: List[List[int]]) -> float:
        current_time = 0
        total_waiting_time = 0
        
        for arrival, time in customers:
            start_time = max(current_time, arrival)
            finish_time = start_time + time
            total_waiting_time += finish_time - arrival
            current_time = finish_time
        
        return total_waiting_time / len(customers)

In this implementation, current_time keeps track of when the chef becomes available. For each customer, we compute the earliest start time of their order using max(current_time, arrival), calculate the finish time, and increment the cumulative waiting time. Finally, dividing by the number of customers gives the required average.

Go Solution

func averageWaitingTime(customers [][]int) float64 {
    currentTime := 0
    totalWaitingTime := 0
    
    for _, customer := range customers {
        arrival, time := customer[0], customer[1]
        startTime := arrival
        if currentTime > arrival {
            startTime = currentTime
        }
        finishTime := startTime + time
        totalWaitingTime += finishTime - arrival
        currentTime = finishTime
    }
    
    return float64(totalWaitingTime) / float64(len(customers))
}

In Go, we handle integer arithmetic carefully and convert the final sum to float64 before dividing to get a floating-point average. Otherwise, the logic is identical to Python.

Worked Examples

Example 1: [[1,2],[2,5],[4,3]]

Customer	Arrival	Time	Start	Finish	Waiting	Current Time
1	1	2	1	3	2	3
2	2	5	3	8	6	8
3	4	3	8	11	7	11

Average waiting time = (2 + 6 + 7) / 3 = 5.0

Example 2: [[5,2],[5,4],[10,3],[20,1]]

Customer	Arrival	Time	Start	Finish	Waiting	Current Time
1	5	2	5	7	2	7
2	5	4	7	11	6	11
3	10	3	11	14	4	14
4	20	1	20	21	1	21

Average waiting time = (2 + 6 + 4 + 1) / 4 = 3.25

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Iterate once through all customers
Space	O(1)	Only a few variables are used, no extra storage

This algorithm is optimal because it processes each customer exactly once and uses constant space.

Test Cases

# Provided examples
assert abs(Solution().averageWaitingTime([[1,2],[2,5],[4,3]]) - 5.0) < 1e-5  # Example 1
assert abs(Solution().averageWaitingTime([[5,2],[5,4],[10,3],[20,1]]) - 3.25) < 1e-5  # Example 2

# Edge cases
assert abs(Solution().averageWaitingTime([[1,1]]) - 1.0) < 1e-5  # Single customer
assert abs(Solution().averageWaitingTime([[1,2],[1,3],[1,4]]) - 5.0) < 1e-5  # Multiple arrivals at same time
assert abs(Solution().averageWaitingTime([[1,10000],[10001,1]]) - 10000.5) < 1e-5  # Large time values
assert abs(Solution().averageWaitingTime([[1,2],[10,3],[20,4]]) - 3.0) < 1e-5  # Sparse arrivals

Test	Why
Single customer	Validates minimum input
Multiple arrivals at same time	Checks handling of simultaneous arrivals
Large time values	Ensures no integer overflow issues
Sparse arrivals	Verifies chef waits correctly for next customer

Edge Cases

1. Single Customer: If there is only one customer, the waiting time is simply the preparation time. The implementation correctly calculates this because current_time starts at 0, and the algorithm computes finish_time - arrival.
2. Customers Arriving Simultaneously: Multiple customers arriving at the same time can be tricky because the chef can only work on one at a time. Using max(current_time, arrival) ensures that the chef processes them sequentially in the correct order.
3. Large Gaps Between Customers: If the next customer arrives after the chef has been idle, the chef should wait until the customer arrives. This is handled because start_time = max(current_time, arrival) will pick the customer’s arrival