Compute average customer waiting time
Overview
This question evaluates scheduling and queue-management concepts, algorithmic design for optimizing average waiting time, and complexity-analysis skills in coding problem-solving. It is commonly asked in the Coding & Algorithms domain because it probes a mix of conceptual understanding of scheduling trade-offs and practical application skills for implementing efficient, scalable algorithms.
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: (
- If you can choose any waiting order, how would you minimize the average waiting time? (
- Generalize to k chefs and describe your algorithm and complexity.