We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
This is quite a challenging problem with some tricky cases to deal with so some hints are in order. Before reading the hint on how to solve the problem, couple of points to note:
Pizza orders are not listed in the order of arrival. Your program should be able to deal with that.
Assume that if you have an order that has arrived but has a long completion time you should process that order. You don't have to wait for the next order that has much shorter completion time if it hasn't arrived yet. Consider this test case which is slight variation on the test case in the problem:
3
0 9
1 3
2 5
Here you should begin processing the first order right away. You will complete all orders with total wait time of 35 with an average wait time of 35/3 = 11. If you just don't process the first order and wait for the 2nd order then you can finish all orders with a total wait time of 28 with an average of 28/3 = 8. The correct answer is 11 and not 8 for this problem.
Now here's the HINT (Read only after you have struggled with the problem for more than an hour):
a. Maintain two queues. One for all the orders prioritized by arrival time. The second one for all orders prioritized by completion time with the shortest order at the head of the queue.
b. Read all the orders in sequence and fill the arrival time queue (first queue).
c. Have a loop that ticks time.
d. For every time tick in the loop see if there are any orders that have arrived by this time from the first queue. If there are then transfer them to the second queue (ordered by completion time) for processing (cooking).
e. Pick the top order from the second queue to process (cook the pizza). If you process the order then tick the time by the time it takes to cook that pizza. If you didn't have any order to process then tick the time by 1 unit. Keep track of total time to process the orders as you process them.
e. Repeat Steps b to e till all orders are processed.
f. Compute the average wait time and print it.
Hope this much explanation is ok to post on the forum. If this is too much let me know and I can condense it further. If there is an easier way to solve the problem then let me know that too.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Minimum Average Waiting Time
You are viewing a single comment's thread. Return to all comments →
This is quite a challenging problem with some tricky cases to deal with so some hints are in order. Before reading the hint on how to solve the problem, couple of points to note:
Pizza orders are not listed in the order of arrival. Your program should be able to deal with that.
Assume that if you have an order that has arrived but has a long completion time you should process that order. You don't have to wait for the next order that has much shorter completion time if it hasn't arrived yet. Consider this test case which is slight variation on the test case in the problem:
3 0 9 1 3 2 5
Here you should begin processing the first order right away. You will complete all orders with total wait time of 35 with an average wait time of 35/3 = 11. If you just don't process the first order and wait for the 2nd order then you can finish all orders with a total wait time of 28 with an average of 28/3 = 8. The correct answer is 11 and not 8 for this problem.
Now here's the HINT (Read only after you have struggled with the problem for more than an hour):
a. Maintain two queues. One for all the orders prioritized by arrival time. The second one for all orders prioritized by completion time with the shortest order at the head of the queue.
b. Read all the orders in sequence and fill the arrival time queue (first queue).
c. Have a loop that ticks time.
d. For every time tick in the loop see if there are any orders that have arrived by this time from the first queue. If there are then transfer them to the second queue (ordered by completion time) for processing (cooking).
e. Pick the top order from the second queue to process (cook the pizza). If you process the order then tick the time by the time it takes to cook that pizza. If you didn't have any order to process then tick the time by 1 unit. Keep track of total time to process the orders as you process them.
e. Repeat Steps b to e till all orders are processed.
f. Compute the average wait time and print it.
Hope this much explanation is ok to post on the forum. If this is too much let me know and I can condense it further. If there is an easier way to solve the problem then let me know that too.