Hackerrank Weekly Challenge #6 // Problem 3

Problem statement

You have to handle $n \leq 10^5$ customers. The $i$-th customer arrives at time $t_i$ and the time of handling him is $l_i$. You are allowed to handle only one customer at the time. The task is to return the average time of waiting for all customers. You have to do it on-line, i.e. when customer arrives, you don't know anything about possible future orders. An interesting fact is when the problem is off-line, then it's $NP$-complete as discussed here. The full problem statement is here.

Solution

When greedy solution works, go for it.

We'll compute the total time of waiting and divide it by $n$ at the end. First, sort all events by the time of arriving and break ties by the time of handling.

The greedy rule here is the following:

Because the problem is off-line, we know that we have to handle the customer which arrives first without delaying his order. When many, let's say $k$, customers arrive at the same time, it's better to handle the one with the minimal time of handling, because the time of handling of the first order you handle adds up to the remaining $(k -1)$ customers as a waiting time. While we are handling a customer, new customers may arrive and each of them has to wait until we finish with the current one. As soon as we finish handling the current customer, we have to deal with remaining ones and we can think of them as of customers which arrived in the same time in which we finished with the current one (they've been already waiting from the time they arrived) and we already know how solve it. When there are no waiting customers, then the next one is again the first one which arrives after we deal with previous orders.

The time complexity of that solution is $O(n \cdot \log n)$, because of sorting at the beginning and a priority queue to keep order of waiting customers.

You can look at my code here.