Problem Description

You have a restaurant with one chef who can only cook for one customer at a time. You're given an array customers where each element customers[i] = [arrival_i, time_i] represents:

• arrival_i: when the i-th customer arrives (sorted in non-decreasing order)
• time_i: how long it takes to prepare the i-th customer's order

The process works as follows:

1. When a customer arrives, they immediately give their order to the chef
2. The chef starts cooking only when idle (not cooking for another customer)
3. Customers must wait until their order is completely prepared
4. The chef must serve customers in the exact order they appear in the input array

The waiting time for each customer is calculated as: the time when their order is completed minus their arrival time.

Your task is to find the average waiting time across all customers. The answer should be accurate within 10^-5.

For example, if we have customers [[1,2], [2,5], [4,3]]:

• Customer 0 arrives at time 1, chef starts immediately, finishes at time 3. Wait time = 3 - 1 = 2
• Customer 1 arrives at time 2, but chef is busy until time 3, then cooks for 5 minutes, finishes at time 8. Wait time = 8 - 2 = 6
• Customer 2 arrives at time 4, but chef is busy until time 8, then cooks for 3 minutes, finishes at time 11. Wait time = 11 - 4 = 7
• Average waiting time = (2 + 6 + 7) / 3 = 5.0

The solution tracks the chef's completion time t and accumulates total waiting time. For each customer, it updates t = max(t, arrival) + cooking_time to handle both cases: when the chef is idle (takes the arrival time) or busy (continues from current time), then adds the waiting time t - arrival to the total.

Intuition

The key insight is that we need to track when the chef becomes available after completing each order. Since customers must be served in the given order, we can process them sequentially.

Think of it like a timeline where the chef has a "current availability time". When a new customer arrives, two scenarios can happen:

1. Chef is idle: If the chef finished the previous order before the current customer arrives, they can start cooking immediately. The chef's new availability time becomes arrival_time + cooking_time.

2. Chef is busy: If the chef is still cooking when the customer arrives, the customer must wait. The chef starts this order right after finishing the previous one, so their new availability time becomes current_availability + cooking_time.

We can capture both scenarios with a single expression: t = max(t, arrival) + cooking_time, where t tracks when the chef finishes the current order.

For calculating waiting time, each customer waits from their arrival until their order is complete. This is simply completion_time - arrival_time, which equals t - arrival after processing each customer.

By maintaining a running sum of all waiting times and dividing by the number of customers at the end, we get the average. This approach is efficient because we only need one pass through the array, processing each customer in order while updating our chef's availability time and accumulating the total wait.

The beauty of max(t, a) is that it automatically handles the decision: if t > a (chef busy), we use t; if t <= a (chef idle), we use a. This eliminates the need for conditional logic and makes the code cleaner.

Solution Approach

We implement a simulation approach that processes customers in order while tracking the chef's availability.

Variables Used:

• tot: Accumulates the total waiting time of all customers
• t: Tracks when the chef finishes the current order (chef's availability time)
• Both start at 0

Algorithm Steps:

1. Iterate through each customer [a, b] where a is arrival time and b is cooking time:

2. Update chef's completion time:

   t = max(t, a) + b

   • max(t, a) determines when the chef can start cooking:
     • If t <= a: Chef is idle, starts at arrival time a
     • If t > a: Chef is busy, continues from current time t
   • Adding b gives the completion time for this order

3. Calculate and accumulate waiting time:

   tot += t - a

   • Waiting time = completion time - arrival time
   • This is t - a for the current customer

4. Return the average:

   return tot / len(customers)

Example Walkthrough:

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

• Customer 0: a=1, b=2

  • t = max(0, 1) + 2 = 3
  • Wait = 3 - 1 = 2
  • tot = 2

• Customer 1: a=2, b=5

  • t = max(3, 2) + 5 = 8
  • Wait = 8 - 2 = 6
  • tot = 8

• Customer 2: a=4, b=3

  • t = max(8, 4) + 3 = 11
  • Wait = 11 - 4 = 7
  • tot = 15

• Average = 15 / 3 = 5.0

The time complexity is O(n) where n is the number of customers, as we process each customer once. The space complexity is O(1) as we only use a fixed amount of extra space.

Example Walkthrough

Let's walk through a small example with customers = [[2,3], [6,2], [8,5]] to illustrate how the solution tracks the chef's availability and calculates waiting times.

Initial State:

• tot = 0 (total waiting time)
• t = 0 (chef's availability time)

Processing Customer 0: [arrival=2, cooking=3]

• Chef's new completion time: t = max(0, 2) + 3 = 5
  • Since t=0 < arrival=2, chef is idle and starts at time 2
  • Finishes at time 2 + 3 = 5
• Customer's waiting time: 5 - 2 = 3
• Update total: tot = 0 + 3 = 3

Processing Customer 1: [arrival=6, cooking=2]

• Chef's new completion time: t = max(5, 6) + 2 = 8
  • Since t=5 < arrival=6, chef is idle when customer arrives
  • Starts at time 6, finishes at time 6 + 2 = 8
• Customer's waiting time: 8 - 6 = 2
• Update total: tot = 3 + 2 = 5

Processing Customer 2: [arrival=8, cooking=5]

• Chef's new completion time: t = max(8, 8) + 5 = 13
  • Since t=8 = arrival=8, chef just finished and can start immediately
  • Starts at time 8, finishes at time 8 + 5 = 13
• Customer's waiting time: 13 - 8 = 5
• Update total: tot = 5 + 5 = 10

Final Result:

• Average waiting time = tot / len(customers) = 10 / 3 = 3.333...

The key insight demonstrated here is how max(t, arrival) elegantly handles both scenarios: when the chef is idle (customers 0 and 1) and when the chef finishes exactly as a customer arrives (customer 2). The chef's completion time t acts as a running timeline that ensures orders are processed sequentially while correctly calculating each customer's wait.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the length of the customers array. The algorithm iterates through the customers array exactly once with a single for loop. Inside the loop, all operations (max(), addition, and subtraction) are constant time O(1) operations. Therefore, the overall time complexity is linear with respect to the number of customers.

Space Complexity: O(1). The algorithm uses only a fixed amount of extra space regardless of the input size. It maintains only two variables (tot and t) to track the cumulative waiting time and the current time respectively. These variables do not scale with the input size, resulting in constant space complexity.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Integer Division Instead of Float Division

A common mistake is performing integer division when calculating the average, which can lead to incorrect results in languages that distinguish between integer and float division.

Pitfall Example:

# Wrong in Python 2 or some other languages
return total_waiting_time // len(customers)  # Integer division

Solution:

# Correct - ensures float division
return total_waiting_time / len(customers)  # Float division in Python 3
# Or explicitly convert to float
return float(total_waiting_time) / len(customers)

2. Not Handling the Chef's Continuous Timeline

Some might incorrectly reset the chef's time or fail to track when the chef finishes the previous order, leading to overlapping cooking times.

Pitfall Example:

for arrival_time, cooking_time in customers:
    # Wrong: Always starts at arrival time, ignoring if chef is busy
    completion_time = arrival_time + cooking_time
    waiting_time = completion_time - arrival_time

Solution:

for arrival_time, cooking_time in customers:
    # Correct: Chef can only start after finishing previous order
    current_time = max(current_time, arrival_time) + cooking_time
    waiting_time = current_time - arrival_time

3. Confusing Waiting Time with Service Time

Mixing up the waiting time (completion - arrival) with just the cooking time can give wrong results.

Pitfall Example:

for arrival_time, cooking_time in customers:
    current_time = max(current_time, arrival_time) + cooking_time
    # Wrong: Adding cooking time instead of actual waiting time
    total_waiting_time += cooking_time

Solution:

for arrival_time, cooking_time in customers:
    current_time = max(current_time, arrival_time) + cooking_time
    # Correct: Waiting time is from arrival to completion
    total_waiting_time += current_time - arrival_time

4. Overflow Issues with Large Numbers

When dealing with very large arrival times or cooking times, integer overflow might occur in some languages.

Solution:

• Use appropriate data types (e.g., long in Java/C++)
• In Python, this is handled automatically with arbitrary precision integers
• Consider using double/float for accumulation if precision requirements allow

5. Edge Case: Empty Customer Array

Not checking for an empty array can cause division by zero error.

Pitfall Example:

def averageWaitingTime(self, customers):
    total_waiting_time = 0
    current_time = 0
  
    for arrival_time, cooking_time in customers:
        # ... calculation logic
  
    # Potential division by zero if customers is empty
    return total_waiting_time / len(customers)

Solution:

def averageWaitingTime(self, customers):
    if not customers:
        return 0.0
  
    total_waiting_time = 0
    current_time = 0
  
    for arrival_time, cooking_time in customers:
        # ... calculation logic
  
    return total_waiting_time / len(customers)