Minimum Average waiting time| Heap
Task (Hard)
Tieu owns a pizza restaurant and he manages it in his own way. While in a normal restaurant, a customer is served by following the first-come, first-served rule, Tieu simply minimizes the average waiting time of his customers. So he gets to decide who is served first, regardless of how sooner or later a person comes.
Different kinds of pizzas take different amounts of time to cook. Also, once he starts cooking a pizza, he cannot cook another pizza until the first pizza is completely cooked. Let's say we have three customers who come at time t = 0 t = 1 Bt = 2 respectively, and the time needed to cook their pizzas is 3, 9, & 6 respectively. If Tieu applies first-come, first- served rule, then the waiting time of three customers is 3, 11, & 16 respectively. The average waiting time in this case is (3 + 11 + 16) / 3 = 10 This is not an optimized solution. After serving the first customer at time t = 3 Tieu can choose to serve the third customer. In that case, the waiting time will be 3, 7, & 17 respectively. Hence the average waiting time is (3 + 7 + 17) / 3 = Q
Help Tieu achieve the minimum average walting time. For the sake of simplicity, just find the integer part of the minimum average waiting time.
Input Format
• The first line contains an Integer N, which is the number of customers.
In the next N lines, the ith line contains two space separated numbers Ti and L. Ti is the time when ith customer order a pizza, and L., is the time required to cook that pizza.
•The customer is not the customer arriving at the arrival time.
Output Format
• Display the integer part of the minimum average waiting time.
Constraints
• 1≤ N ≤ 105
Note
• The waiting time is calculated as the difference between the time a customer orders pizza (the time at which they enter the shop) and the time she is served.
• Cook does not know about the future orders.
Sample Input 0
3
19
26
Sample Output 0
9
Sample Input 1
3
19
25
Sample Output 1
8
Explanation 1
Let's call the person ordering at time = 0 as A, time = 1 as B and time = 2 as C. By delivering pizza for A, C and B we get the minimum average wait time to be
(3+6+16)/3 = 25/3 = 8.33
the integer part is 8 and hence the answer.
F1
F2
+
X
SOLUTION 1
def minimumAverage(customers):
# Customers is a list of tuples. I assume it's already
# sorted by i[0], the arrival time, but let's make sure.
# We'll also need to know the total customer number in
# order to calculate the average wait later on.
customers.sort()
cust_count = len(customers)
# Since the minimum average wait will always be reached
# by preparing the quickest pizza first, we want to store
# the pizzas in a min heap sorted by required cook time.
# As we start cooking, we'll pull customers off the list
# and put them into a heap of waiting customers. We'll
# also need to track time throughout the process to know
# when to add to the heap or remove from it. And since
# we're calculating average using the total number of
# customers, we need a variable for total wait time to
# divide by it.
waiting = []
time = 0
wait_time = 0
# This whole process will run until there are no more
# customers in either list.
while customers or waiting:
# Move customers to waiting once they've ordered.
# Flip tuple values for correct priority sort.
while customers and time >= customers[0][0]:
t_order, t_cook = customers.pop(0)
heapq.heappush(waiting, (t_cook, t_order))
# If we're waiting for orders, jump to the next.
if len(waiting) == 0:
time = customers[0][0]
continue
# We don't want to move one second at a time as
# that would confuse priority. We want to think
# of time in the form of pizzas cooked. So,
# instead of incrementing time, we'll add the
# cook time of the highest priority pizza, one at
# a time. That will give the time the customer is
# served, from which we subtract their order time
# to know their wait and add it to the total wait.
cook, order = heapq.heappop(waiting)
time += cook
wait_time += (time - order)
# Use // to return only the integer part of avg time.
return wait_time // cust_count
