Code Implementation

class Solution:
    def averageWaitingTime(self, customers: List[List[int]]) -> float:
        current_time = 0
        total_wait = 0
        for arrival, time in customers:
            # Chef becomes available at max(current_time, arrival)
            start = max(current_time, arrival)
            finish = start + time
            total_wait += finish - arrival
            current_time = finish
        return total_wait / len(customers)
      

class Solution {
public:
    double averageWaitingTime(vector<vector<int>>& customers) {
        long long currentTime = 0, totalWait = 0;
        for (const auto& c : customers) {
            int arrival = c[0], time = c[1];
            currentTime = max(currentTime, (long long)arrival);
            currentTime += time;
            totalWait += currentTime - arrival;
        }
        return (double)totalWait / customers.size();
    }
};
      

class Solution {
    public double averageWaitingTime(int[][] customers) {
        long currentTime = 0, totalWait = 0;
        for (int[] c : customers) {
            int arrival = c[0], time = c[1];
            currentTime = Math.max(currentTime, arrival);
            currentTime += time;
            totalWait += currentTime - arrival;
        }
        return (double) totalWait / customers.length;
    }
}
      

var averageWaitingTime = function(customers) {
    let currentTime = 0, totalWait = 0;
    for (const [arrival, time] of customers) {
        currentTime = Math.max(currentTime, arrival);
        currentTime += time;
        totalWait += currentTime - arrival;
    }
    return totalWait / customers.length;
};
      

Problem Description

You are given a list of customers, where each customer is represented as a list [arrivalTime, timeNeeded]. Each customer arrives at the restaurant at arrivalTime, and it takes timeNeeded units of time to prepare their order. The chef can only serve one customer at a time and starts working on the next customer as soon as possible (either when the previous order is done or when the customer arrives, whichever is later).

The waiting time for each customer is defined as the time from their arrival to when their order is complete. Your task is to calculate and return the average waiting time for all customers.

Constraints:

• Each customer is only served once, in the given order.
• No customer is skipped or reordered.
• All times are positive integers.

Thought Process

At first glance, the problem seems to require simulating a queue at a restaurant. For each customer, you need to keep track of when the chef is available and how long the customer waits. A brute-force approach might involve simulating every single time unit, but this isn't necessary since the chef can only work on one order at a time, and the customers arrive in a given sequence.

The key insight is that for each customer, their actual waiting time depends on whether the chef is already idle or still busy with the previous order when they arrive. The chef's current time is either the finish time of the last order or the arrival time of the customer, whichever is greater.

Instead of tracking every time unit, we only need to track:

• The chef's current available time
• The total waiting time accumulated so far

Solution Approach

Let's break down the solution step by step:

1. Initialize Variables:
   • current_time: Tracks when the chef is next available (initially 0).
   • total_wait: Accumulates the total waiting time for all customers.
2. Iterate Through Customers:
   • For each customer, get their arrival and time_needed.
   • The chef will start the order at max(current_time, arrival).
   • The order finishes at start_time + time_needed.
   • The customer's waiting time is finish_time - arrival.
   • Update current_time to finish_time.
   • Add the waiting time to total_wait.
3. Compute the Average:
   • Return total_wait / number_of_customers as a floating-point number.

This approach is efficient because:

• We process each customer exactly once (O(n) time).
• No extra data structures are needed beyond a few variables (O(1) space).

Example Walkthrough

Let's consider the following input:

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

1. Customer 1:
   • Arrives at 1, needs 2 units of time.
   • Chef is available at 0, so starts at max(0, 1) = 1.
   • Finishes at 1 + 2 = 3.
   • Waiting time: 3 - 1 = 2.
   • Update current_time = 3, total_wait = 2.
2. Customer 2:
   • Arrives at 2, needs 5 units of time.
   • Chef is available at 3, so starts at max(3, 2) = 3.
   • Finishes at 3 + 5 = 8.
   • Waiting time: 8 - 2 = 6.
   • Update current_time = 8, total_wait = 8.
3. Customer 3:
   • Arrives at 4, needs 3 units of time.
   • Chef is available at 8, so starts at max(8, 4) = 8.
   • Finishes at 8 + 3 = 11.
   • Waiting time: 11 - 4 = 7.
   • Update current_time = 11, total_wait = 15.

Final average waiting time: 15 / 3 = 5.0

Time and Space Complexity

Brute-force approach:

• If we tried to simulate every time unit, the time complexity would be O(T), where T is the total time span (could be very large).
• Space complexity would also be high if we stored each time unit's state.

• Time complexity: O(n), where n is the number of customers. We process each customer once.
• Space complexity: O(1), as we only use a few variables regardless of input size.

This efficiency comes from only tracking when the chef is available and updating totals as we process each customer.

Summary

The Average Waiting Time problem is a simulation of a simple queue, where each customer's wait depends on the chef's availability and their own arrival. By keeping track of the chef's current time and each customer's waiting time, we can efficiently compute the average without simulating each time unit. The solution is both simple and efficient, running in linear time with constant space, and demonstrates how understanding the problem's structure allows us to avoid unnecessary computation.