Compute average customer waiting time

You are given n customer orders; each order i = [a_i, p_i] where a_i is the arrival time and p_i is the preparation time. A single chef processes orders non-preemptively. If the chef is idle and multiple orders are available, they pick the earliest-arrived order among those waiting. Compute the average waiting time across all customers, where waiting_i = finish_i − a_i. Return a floating-point value. Constraints: 1 ≤ n ≤ 100000; 0 ≤ a_i < 1e9; 1 ≤ p_i ≤ 1e4. Follow-ups: (1) If you can choose any waiting order, how would you minimize the average waiting time? (2) Generalize to k chefs and describe your algorithm and complexity.

What a Strong Answer Covers

• A clear algorithm with the right data structures and enough pseudocode or code-level detail to implement it.
• A correctness argument that explains why the algorithm covers all required cases.
• Time and space complexity, plus at least one alternative approach when relevant.
• Focused tests for normal cases, edge cases, and failure modes.

Follow-up Questions

• How would the approach change if the input were streaming or too large for memory?
• What invariants would you assert in production code?
• Which tests would catch off-by-one, duplicate, or tie-breaking bugs?

Compute Average Customer Waiting Time

You are given n customer orders. Each order i = [a_i, p_i], where a_i is the arrival time and p_i is the preparation time. A single chef processes orders non-preemptively (once started, an order runs to completion). When the chef is idle and one or more orders have already arrived, the chef picks the earliest-arrived order among those waiting (ties broken by smaller preparation time, then by input order). If no order has arrived yet, the chef waits until the next arrival.

The waiting time of a customer is waiting_i = finish_i - a_i, where finish_i is the time the chef completes that order. Return the average waiting time across all customers as a floating-point value.

Example

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

• Order 0 arrives at 1, chef idle, starts at 1, finishes at 3 → wait 2.
• Order 1 arrived at 2 (waiting since the chef was busy), starts at 3, finishes at 8 → wait 6.
• Order 2 arrived at 4, starts at 8, finishes at 11 → wait 7.
• Average = (2 + 6 + 7) / 3 = 5.0.

Constraints

• 1 <= n <= 100000
• 0 <= a_i < 1e9 (arrival time)
• 1 <= p_i <= 1e4 (preparation time)
• The chef processes orders non-preemptively.
• When idle, the chef picks the earliest-arrived order among those that have already arrived.

Hints

1. Sort orders by arrival time. Sweep a clock forward, and whenever the chef is free, only orders that have already arrived are eligible.
2. Use a min-heap of waiting orders keyed by arrival time so you can quickly grab the earliest-arrived one. When the heap is empty, fast-forward the clock to the next arrival.
3. Waiting time for an order is finish_time - arrival_time, where finish_time is the clock value right after the chef completes it. Sum these and divide by n.

Solution

Solution Alignment

The prompt asks for an implementation-level answer. The safest way to present it is to define the state, maintain clear invariants, then walk through complexity and tests.

Problem Restatement

You are given n customer orders; each order i = [a_i, p_i] where a_i is the arrival time and p_i is the preparation time. A single chef processes orders non-preemptively. If the chef is idle and multiple orders are available, they pick the earliest-arrived order among those waiting. Compute the average waiting time across all customers, where waiting_i = finish_i − a_i. Return a floating-point value. Constraints: 1 ≤ n ≤ 100000; 0 ≤ a_i < 1e9; 1 ≤ p_i ≤ 1e4. Follow-ups: ( 1) If you can choose any waiting order, how would you minimize the average waiting time? ( 2) Generalize to k chefs and describe your algorithm and complexity.

Recommended Approach

Start with a brute-force baseline to confirm correctness, then identify the repeated work or ordering property that enables a better data structure such as a hash map, heap, stack, queue, two pointers, prefix sums, BFS/DFS, or dynamic programming. Write the implementation around a small invariant and test that invariant directly.

Correctness

The implementation should maintain an invariant after each loop or operation that directly matches the problem statement. At termination, that invariant implies the returned value has considered every valid candidate exactly once, or has preserved the required data-structure state after every API call.

Complexity

State the baseline complexity and the optimized complexity. For most interview constraints, justify why the optimized approach meets the expected input size.

Edge Cases and Tests

Empty and singleton inputs, duplicates, ties, invalid inputs, boundary values, and tests that exercise the main invariant.