Recent CP News

Minimum Average Waiting Time for Pizza || Hard Problem

It’s Time for Pizza

Dude It’s Time for Pizza (;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, & t=2 respectively, and the time needed to cook their pizzas is 3, 9, & 6 respectively. If Tieu applies first-come, the 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 = 9.

Help Tieu achieve the minimum average waiting 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 Li. Ti is the time when ith customer order a pizza, and Li is the time required to cook that pizza.
  • The ith customer is not the customer arriving at the ith arrival time.

Output Format

  • Display the integer part of the minimum average waiting time.

Constraints

  • 1 ≤ N ≤ 105
  • 0 ≤ Ti ≤ 109
  • 1 ≤ Li ≤ 109

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 #00

3
0 3
1 9
2 6

Sample Output #00

9

Explanation #01

Let’s call the person ordering at time = 0 as A, time = 1 as B and time = 2 as C. By delivering pizza for AC 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.

Solution with Explanation

This problem can be solved using a greedy approach.

We have to remember that Tieu cannot know about future orders beforehand. So he will have to serve one of the orders that are currently waiting to be served. But how should he decide which order to serve now ?

This is where the greedy approach comes. He should always serve the order which has minimum cooking time i.e. the order with the minimum L.Let’s prove this approach to be the optimal strategy using proof by contradiction.

Proof by contradiction:

Let’s say currently we have X orders that need to be served. Let Lmin be the cooking time of the order with the minimum cooking time. Then if we decide to serve this order now, it will contribute (X * Lmin + C1) time to the total waiting time, where C1 is the time waited by new customers who have placed orders while we were cooking this order.

Now let’s say, it was actually optimal to serve the jth order where Lj>Lmin.Then this will contribute (X*Lj+C2) time to the total waiting time, where C2 s the time waited by new customers who have placed orders while we were cooking the jth order. Now we have,

  1. Lj>Lmin
  2. C2>C1 (Since the jth  order takes more time to be cooked, the number of new customers who have placed order in the mean time will be higher or equal to the first scenario and they will have to wait more time as Lj>Lmin)

So we can conclude that,

(XLmin+C1)<(XLj+C2)

But this is a contradiction to the claim that serving the jth order with Lj>Lmin, is optional.Hence, using

proof by contradiction, serving the order with the lowest cooking time is proved to be the optimal strategy.

Storing the data efficiently:

At first, we need to sort the orders according to increasing order time. An array is sufficient here. But then we need to store the currently available orders according to increasing cooking time. We can use a min heap for this purpose. We will loop through the array. Upon arriving at the ith  order, we will insert it into the min heap if its order time is less than or equal to the current time. Otherwise, we will keep serving from the top of the heap until current time becomes larger than or equal to the order time of the ith order or the heap becomes empty. We will update the current time while inserting an order into the heap ( if needed ) and also while serving an order.

Editorialist’s solution

C++

#include<bits/stdc++.h>
using namespace std;

typedef long long int LL;

int n;
struct order{
    LL T, L;
}customer[100010];

bool operator < (order a, order b)
{
    return a.T < b.T;
}

bool compare(order a, order b)
{
    return a.L > b.L;
}
priority_queue<order, vector<order>, function<bool(order, order)>> min_heap(compare);

void add_order(order current_order, LL &current_time)
{
    if(min_heap.empty() == true)
        current_time = max(current_time, current_order.T);
    min_heap.push(current_order);
}

LL serve_order(LL &current_time)
{
    order current_order = min_heap.top();
    min_heap.pop();
    current_time += current_order.L;
    return current_time - current_order.T;
}

LL solve(int n)
{
    LL current_time = 0, total_waiting_time = 0;
    for(int i = 1; i<=n; i++)
    {
        if(i == 1 || customer[i].T <= current_time)
            add_order(customer[i], current_time);
        else if(min_heap.empty() == false)
        {
            while(min_heap.empty() == false && customer[i].T > current_time)
                total_waiting_time += serve_order(current_time);
            add_order(customer[i], current_time);
        }
    }
    while(min_heap.empty() == false)
        total_waiting_time += serve_order(current_time);
    return total_waiting_time/n;
}
int main()
{
    cin >> n;
    for(int i = 1; i<=n; i++)
        cin >> customer[i].T >> customer[i].L ;
    sort(customer+1, customer+n+1);
    cout << solve(n) << endl;
    return 0;
}

{Code With Codeater}

Give Your Reviews




Leave a Reply