Average Waiting Time: Greedy Simulation

There is a restaurant with a single chef. You are given an array customers where customers[i] = [arrival_i, time_i]. The i-th customer arrives at time arrival_i, and the chef takes time_i units to prepare their order. The chef can only prepare one order at a time and works on orders in the order they arrive. If the chef is busy when a customer arrives, that customer has to wait. Return the average waiting time across all customers, where waiting time is the time between arrival and when the order is finished.

This is LeetCode 1701: Average Waiting Time, a medium problem that teaches the simulation pattern for sequential processing. The key is tracking when the chef becomes free and understanding that customers who arrive while the chef is busy must wait in line.

Why this problem matters

Average Waiting Time is a clean example of the sequential processing simulation. You have a single resource (the chef) and a queue of tasks (customer orders) that must be handled in order. This pattern appears everywhere in systems design and scheduling: CPU task queues, printer spoolers, API request handling, and network packet processing.

The problem also teaches you to think about the difference between "when a task is submitted" and "when a task actually starts." That gap is the idle waiting time, and it depends entirely on how backed up the resource is. Learning to model this gap precisely is a building block for more complex scheduling problems like Task Scheduler (LeetCode 621) and Process Tasks Using Servers (LeetCode 1882).

The key insight

You only need one variable beyond the loop: current_time, which tracks when the chef becomes free. For each customer, the chef cannot start before either (a) the chef finishes the previous order or (b) the customer arrives. So the chef starts at max(current_time, arrival).

Once the chef starts, the finish time is simply start + time_needed. The customer's waiting time is finish - arrival, which captures both idle waiting (if the chef was busy) and cooking time.

That is the entire algorithm. No priority queue, no sorting, no complex state. Just one running variable updated in a single pass.

The solution

def average_waiting_time(customers):
    current_time = 0
    total_wait = 0

    for arrival, time_needed in customers:
        start = max(current_time, arrival)
        finish = start + time_needed
        total_wait += finish - arrival
        current_time = finish

    return total_wait / len(customers)

Here is what each piece does:

1. current_time tracks when the chef finishes the current order and becomes available. It starts at 0 (the chef is free from the beginning).
2. For each customer, start = max(current_time, arrival) picks the later of "chef is free" or "customer has arrived." If the chef is already free when the customer shows up, cooking starts immediately. If the chef is still busy, the customer waits.
3. finish = start + time_needed is when the order is done.
4. finish - arrival is the total time the customer spent in the restaurant, from walking in to getting their food. This includes both idle waiting and cooking.
5. After processing all customers, divide the total wait by the number of customers to get the average.

Visual walkthrough

Let's trace through customers = [[1,2],[2,5],[4,3]] step by step. Watch how current_time advances and how each customer's waiting time accumulates.

Notice how Customer 1 arrives at time 2 but the chef is busy until time 3, so they wait one extra unit before cooking even begins. Customer 2 arrives at time 4 but the chef is not free until time 8, adding four units of idle waiting. These gaps are what make the average waiting time higher than the average cooking time.

Complexity analysis

This is optimal. You must look at every customer at least once to compute the average, so O(n) is the lower bound. And O(1) space means no extra data structures at all.

The building blocks

This problem is built on two reusable patterns that CodeBricks drills independently.

1. Sequential simulation with a running clock

The pattern of processing tasks in order while tracking a single "current time" variable:

current_time = 0
for task in tasks:
    start = max(current_time, task.ready_time)
    end = start + task.duration
    current_time = end

In Average Waiting Time, the tasks are customer orders and the clock tracks the chef. In problems like "Car Pooling" or "Meeting Rooms," the clock tracks capacity or room availability. The skeleton is the same: advance a clock based on when the next task can actually begin, not just when it was submitted.

2. Running accumulator for averages

The pattern of accumulating a total across all items and dividing at the end:

total = 0
for item in items:
    total += compute_value(item)
return total / len(items)

This avoids floating-point drift from computing a running average. Accumulate integers (or exact values) first, then divide once. You see this in problems that ask for averages, expected values, or normalized scores. It is simple but important to get right, especially in languages where integer division behaves differently from float division.

Edge cases

Before submitting, make sure your solution handles these:

• Single customer [[1, 5]]: chef starts at 1, finishes at 6. Wait = 5. Average = 5.0.
• No idle time: customers arrive far enough apart that the chef is always free. Each customer's wait equals their cooking time. Example: [[1,2],[10,3]]. Wait = 2 + 3 = 5, average = 2.5.
• All customers arrive at the same time [[0,3],[0,4],[0,5]]: chef finishes at 3, 7, 12. Waits = 3, 7, 12. Average = 22 / 3 = 7.33.
• Customer arrives exactly when chef finishes: [[0,2],[2,3]]. Chef finishes first order at 2, customer 1 arrives at 2. max(2, 2) = 2, no idle wait. Cooking starts immediately.
• Large cooking times: a customer with time_needed = 10^9 is fine. The algorithm uses only addition and max, no overflow risk in Python.

The simulation handles all of these without special-case logic.

From understanding to recall

You have read the simulation and it makes sense. One variable, one loop, one max call. Clean. But can you write it from scratch in an interview without looking at it?

The details matter: using max(current_time, arrival) instead of just current_time, remembering to accumulate finish - arrival (not finish - start), and dividing by len(customers) at the end instead of maintaining a running average. These are small but critical, and they are easy to get wrong under pressure if you have not practiced writing them from memory.

Spaced repetition closes that gap. You practice writing the sequential simulation loop from scratch at increasing intervals. After a few rounds, the pattern is automatic. You see "process tasks in order, compute average wait" and the code flows out without hesitation.

The sequential simulation pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping they stick.

Related posts

• Task Scheduler - A more complex scheduling problem where you must handle cooldowns between identical tasks
• Gas Station - Greedy simulation with a running accumulator and reset logic
• Lemonade Change - Sequential processing where each step depends on the accumulated state from previous steps

CodeBricks breaks the average waiting time LeetCode problem into its sequential simulation and running accumulator building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a simulation question shows up in your interview, you do not think about it. You just write it.