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.


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.

  • Hari

    Why is it true that "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 ... "? Should't the waiting time be from the moment a customer orders?

    • http://chasethered.com pkacprzak

      Yes of course, I wrote "While we are handling a customer, new customers may arrive and each of them has to wait until we finish with the current one", so the waiting time adds up. I updated the sentence that you pointed and I hope it's more accurate right now.

  • Guest

    doesn't work

    take this ex:

    t=0 customer 'a' arrives with handling time 1000 and
    at t=1 customer 'b' arrives with handling time 1

    your solution would schedule it as a,b in that order. the answer here would be (1000+1000)/2

    whereas if we schedule it as b,a the answer would be (1002+1)/2

    • http://chasethered.com pkacprzak

      Problem statement says that we don't know about future orders, so if someone arrives at time t and we are not handling any orders at this time, then we have to handle that customer, because we don't know if someone else arrives later.