⚡Flashcard Drill➔
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

  1. Simulate the chef's clock: cur is the time at which the chef becomes free.
  2. For each customer, the chef starts at max(cur, arrival), so the finish time is max(cur, arrival) + time.
  3. The waiting time for that customer is finish - arrival.
  4. 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 += t without the max: the chef would be modelled as starting immediately even if the customer has not arrived, which is impossible.
  • Summing cur - arrival incorrectly for the first customer: the formula handles it, since cur starts at 0 and max(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.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems