Sponsored
Sponsored
This approach involves simulating the process: for each customer, determine when their order can start based on the current time (when the previous order finishes) and calculate their waiting time.
You'll need to track the current time and update it as each order is processed.
Time Complexity: O(n) because we iterate over the customers.
Space Complexity: O(1) as we use a constant space.
1def average_waiting_time(customers):
2 current_time = 0
3 total_waiting_time = 0.0
4 for arrival, time in customers:
5 current_time = max(current_time, arrival) + time
6 total_waiting_time += current_time - arrival
7 return total_waiting_time / len(customers)
8
9customers = [[1, 2], [2, 5], [4, 3]]
10print(f"{average_waiting_time(customers):.5f}")The Python function works by iterating each order, computing the waiting times using inline tuple unpacking for efficiency, accumulating total time, and then returning the average.
In scenarios with dynamic restaurant workflows, using event simulation with a priority queue could be beneficial. Here, though all customers wait in order, this method can plan for potential future complexity.
This approach is more efficient when prioritizing different jobs based on arrival or cooking time in expanded contexts.
Time Complexity: O(n log n) due to priority queue operations.
Space Complexity: O(n) for the queue population.
1#include <iostream>
2#include <vector>
3#include <queue>
4#include <utility>
5
6float averageWaitingTime(std::vector<std::pair<int,int>>& customers) {
7 int currentTime = 0;
float totalWaitingTime = 0.0;
std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> pq;
for(auto& customer : customers) {
pq.push(customer);
}
while (!pq.empty()) {
auto customer = pq.top(); pq.pop();
int arrival = customer.first;
int time = customer.second;
currentTime = std::max(currentTime, arrival) + time;
totalWaitingTime += currentTime - arrival;
}
return totalWaitingTime / customers.size();
}
int main() {
std::vector<std::pair<int, int>> customers = {{1,2},{2,5},{4,3}};
std::cout << std::fixed << std::setprecision(5) << averageWaitingTime(customers) << std::endl;
return 0;
}This C++ solution utilizes a priority queue, simulating an event-driven strategy. Although it prioritizes emissions less efficiently for this fixed input, the template demonstrates adaptability for more assorted queues and orders beyond the current sorting constraints.