NeetCode #91LC-1701MediumArrays & Hashing
← Back to All Problems#91 · #1701 · Average Waiting Time(平均等待时间)
📌 Problem Statement & Constraints
There is a single chef. Given
customers[i] = [arrival_i, time_i], the chef starts cooking customer i's order no earlier than arrival_i and after finishing the previous order, and takes time_i to finish. Return the average waiting time over all customers. Constraints: 1 <= customers.length <= 10^5; customers is sorted by arrival time.💡 Core Algorithmic Approaches
- Simulate the chef's clock:
curis the time at which the chef becomes free. - For each customer, the chef starts at
max(cur, arrival), so the finish time ismax(cur, arrival) + time. - The waiting time for that customer is
finish - arrival. - Accumulate the waiting times and divide by the number of customers. Because the input is sorted by arrival, one pass is enough.
💻 Benchmark Python3 Implementation
class Solution:
def averageWaitingTime(self, customers: List[List[int]]) -> float:
cur = 0 # when the chef becomes free
total = 0
for arrival, t in customers:
cur = max(cur, arrival) + t # start no earlier than arrival
total += cur - arrival # waiting time for this customer
return total / len(customers)⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): one pass.
💾 Space Complexity
O(1): two accumulators.
⚠️ Interview Pitfalls & Follow-ups
- Using
cur += twithout themax: the chef would be modelled as starting immediately even if the customer has not arrived, which is impossible. - Summing
cur - arrivalincorrectly for the first customer: the formula handles it, sincecurstarts at 0 andmax(0, arrival) = arrival. - Returning an integer: the answer is a float; Python's
/is correct. - Re-sorting the customers: the input is already sorted by arrival, so no sort is needed.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.