1701. Average Waiting Time

Problem Statement

There is a restaurant with a single chef. You are given an array customers, where customers[i] = [arrival_i, time_i]:

arrival_i is the arrival time of the ith customer. The arrival times are sorted in non-decreasing order.
time_i is the time needed to prepare the order of the ith customer.

When a customer arrives, he gives his order to the chef, and the chef starts preparing it once he is idle. The customer waits until his order is prepared. The chef does not prepare food for more than one customer at a time. The chef prepares food for customers in the order they were given in the input.

Return the average waiting time of all customers. Solutions within 10^-5 from the actual answer are considered accepted.

Examples

Example 1:

Input: customers = [[1,2],[2,5],[4,3]]
Output: 5.00000
Explanation:
1) 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.
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.
3) 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.00000.

Example 2:

Input: customers = [[5,2],[5,4],[10,3],[20,2]]
Output: 3.25000
Explanation:
1) 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.
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.
3) 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.
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 22, so the waiting time of the fourth customer is 22 - 20 = 2.
So the average waiting time = (2 + 6 + 4 + 2) / 4 = 3.25000.

Constraints

1 <= customers.length <= 10^5
1 <= arrival_i, time_i <= 10^4
arrival_i <= arrival_{i+1} (arrival times are sorted in non-decreasing order)

Clarification Questions

Before diving into the solution, here are 5 important clarifications and assumptions to discuss during an interview:

Single server: Is there only one chef/server processing orders? (Assumption: Yes - single server queue system)
Order processing: Are orders processed in arrival order or can they be reordered? (Assumption: Process in arrival order - FIFO queue)
Waiting time definition: How is waiting time calculated? (Assumption: Waiting time = finish_time - arrival_time, includes both waiting and service time)
Chef availability: What happens if the chef is idle when a customer arrives? (Assumption: Chef starts immediately - no waiting, but service time still counts)
Precision: What precision is required for the average? (Assumption: Return as double with appropriate precision - typically 5 decimal places)

Interview Deduction Process (20 minutes)

Step 1: Brute-Force Approach (5 minutes)

Simulate the queue system step by step. Maintain a timeline and process each customer arrival and service completion as events. Track when each customer arrives, when service starts, and when service ends. Calculate waiting time for each customer and compute the average. This approach works but requires careful event management and can be complex to implement correctly.

Step 2: Semi-Optimized Approach (7 minutes)

Process customers sequentially. Maintain a current time variable. For each customer, if they arrive after the current time, the chef starts immediately at arrival time. If they arrive before the current time, they wait until the chef finishes previous orders. Update current time and accumulate waiting times. This simplifies the simulation by processing in order, avoiding event scheduling complexity.

Step 3: Optimized Solution (8 minutes)

Use a single pass through customers. Maintain the chef’s finish time. For each customer, the start time is max(arrival_time, chef_finish_time). The finish time is start_time + order_time. Waiting time is finish_time - arrival_time. Accumulate total waiting time and divide by number of customers. This achieves O(n) time with O(1) space. The key insight is that we don’t need to simulate events - we can compute start and finish times directly based on the chef’s availability and customer arrivals.

Solution Approach

This problem simulates a single-server queue system where customers arrive and wait for service. The key is to track when the chef becomes available and calculate waiting time for each customer.

Key Insights:

Chef Availability: Chef can start next order only when idle
Waiting Time: waiting_time = finish_time - arrival_time
Finish Time: finish_time = max(chef_free_time, arrival_time) + order_time
Sequential Processing: Orders are processed in the given order

Solution 1: Explicit Simulation (If-Else)

class Solution {
public:
    double averageWaitingTime(vector<vector<int>>& customers) {
        long long t = 0, totalTime = 0;
        for(auto& c: customers) {
            int arrival = c[0], order = c[1];
            if(t > arrival) {
                totalTime += t - arrival;
            } else {
                t = arrival;
            }
            totalTime += order;
            t += order;
        }
        return (double) totalTime / customers.size();
    }
};

Algorithm Explanation:

Initialize Variables:
- t: Current time when chef becomes free (finish time of previous order)
- totalTime: Cumulative waiting time for all customers
Process Each Customer:
- Extract arrival and order time
- If chef is busy (t > arrival):
  - Customer waits: totalTime += t - arrival
- If chef is idle (t <= arrival):
  - Chef starts immediately: t = arrival
- Add order preparation time: totalTime += order
- Update chef free time: t += order
Return Average: totalTime / customers.size()

Example Walkthrough:

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

Customer 1: arrival=1, order=2
  t=0 <= arrival=1 → chef idle, start at 1
  totalTime += 0 (no wait) + 2 (order) = 2
  t = 1 + 2 = 3
  Waiting time: 3 - 1 = 2 ✓

Customer 2: arrival=2, order=5
  t=3 > arrival=2 → chef busy, wait until 3
  totalTime += (3 - 2) = 1 + 5 = 6
  t = 3 + 5 = 8
  Waiting time: 8 - 2 = 6 ✓

Customer 3: arrival=4, order=3
  t=8 > arrival=4 → chef busy, wait until 8
  totalTime += (8 - 4) = 4 + 3 = 7
  t = 8 + 3 = 11
  Waiting time: 11 - 4 = 7 ✓

Average: (2 + 6 + 7) / 3 = 5.0 ✓

Complexity Analysis:

Time Complexity: O(n)
- Single pass through customers array
- Each customer processed in O(1) time
Space Complexity: O(1)
- Only using constant extra variables (t, totalTime)
- No additional data structures

Solution 2: Simplified with `max()` (More Concise)

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

Algorithm Explanation:

Initialize Variables: Same as Solution 1
Process Each Customer:
- Update chef free time: t = max(t, arrival) + order
  - max(t, arrival) ensures chef starts at the later of:
    - When chef becomes free (t)
    - When customer arrives (arrival)
- Calculate waiting time: totalTime += t - arrival
  - t is now the finish time
  - Waiting time = finish time - arrival time
Return Average: totalTime / customers.size()

Key Insight:

The max(t, arrival) elegantly handles both cases:

Chef idle: t <= arrival → start at arrival
Chef busy: t > arrival → start at t

Example Walkthrough:

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

Customer 1: arrival=1, order=2
  t = max(0, 1) + 2 = 1 + 2 = 3
  totalTime += 3 - 1 = 2
  Waiting time: 2 ✓

Customer 2: arrival=2, order=5
  t = max(3, 2) + 5 = 3 + 5 = 8
  totalTime += 8 - 2 = 6
  Waiting time: 6 ✓

Customer 3: arrival=4, order=3
  t = max(8, 4) + 3 = 8 + 3 = 11
  totalTime += 11 - 4 = 7
  Waiting time: 7 ✓

Average: (2 + 6 + 7) / 3 = 5.0 ✓

Complexity Analysis:

Time Complexity: O(n)
- Single pass through customers array
- Each customer processed in O(1) time
Space Complexity: O(1)
- Only using constant extra variables
- More concise than Solution 1

Comparison of Solutions

Solution	Code Length	Readability	Logic Clarity
Solution 1	Longer	More explicit	Clear if-else logic
Solution 2	Shorter	More concise	Elegant `max()` usage

Key Insights

Single Server Queue: Classic queueing theory problem
Sequential Processing: Orders processed in arrival order
Waiting Time Formula: finish_time - arrival_time
Chef Availability: start_time = max(chef_free_time, arrival_time)
Finish Time: finish_time = start_time + order_time

Edge Cases

All customers arrive before chef finishes: Chef always busy
- customers = [[1,10],[2,5],[3,3]]
- Each customer waits for previous to finish
Chef always idle: Customers arrive after chef finishes
- customers = [[1,2],[5,3],[10,1]]
- No waiting time, only order preparation time
Single customer: customers = [[1,5]]
- Waiting time = order time = 5
Simultaneous arrivals: Multiple customers arrive at same time
- customers = [[5,2],[5,4],[5,3]]
- Processed sequentially, later ones wait longer

Common Mistakes

Wrong waiting time calculation: Using start_time - arrival instead of finish_time - arrival
Not handling chef idle case: Assuming chef is always busy
Integer overflow: Not using long long for large sums
Wrong order processing: Processing orders out of sequence
Precision issues: Not using double for division

LC 1834: Single-Threaded CPU - Similar queue processing with priority
LC 1882: Process Tasks Using Servers - Multiple servers, task scheduling
LC 621: Task Scheduler - Task scheduling with cooldown
LC 253: Meeting Rooms II - Resource allocation, similar simulation

This problem demonstrates simulation of a single-server queue system. The key insight is using max(chef_free_time, arrival_time) to determine when the chef can start the next order, elegantly handling both idle and busy states.

Robina Li

1701. Average Waiting Time

1701. Average Waiting Time

Problem Statement

Examples

Constraints

Clarification Questions

Interview Deduction Process (20 minutes)

Solution Approach

Key Insights:

Solution 1: Explicit Simulation (If-Else)

Algorithm Explanation:

Example Walkthrough:

Complexity Analysis:

Solution 2: Simplified with `max()` (More Concise)

Algorithm Explanation:

Key Insight:

Example Walkthrough:

Complexity Analysis:

Comparison of Solutions

Key Insights

Edge Cases

Common Mistakes

Related Posts

Recent Posts

1701. Average Waiting Time

Problem Statement

Examples

Constraints

Clarification Questions

Interview Deduction Process (20 minutes)

Solution Approach

Key Insights:

Solution 1: Explicit Simulation (If-Else)

Algorithm Explanation:

Example Walkthrough:

Complexity Analysis:

Solution 2: Simplified with max() (More Concise)

Algorithm Explanation:

Key Insight:

Example Walkthrough:

Complexity Analysis:

Comparison of Solutions

Key Insights

Edge Cases

Common Mistakes

Related Problems

Related Posts

Recent Posts

Solution 2: Simplified with `max()` (More Concise)