A person provides a service and he/she can serve $k$ clients each minute.

Now, client number $i$ comes at the beginning of minute $a_{i}$ and waits $w_{i}$ minutes to receive the service and if they don't receive the service in the interval $[a_{i}, a_{i} + w_{i}]$, they leave.

If we have $n$ clients, can the person serve all them or not?

My question: Does the above problem have a formal name? I want to write a python code for that but I don't know which keywords should I search?

  • $\begingroup$ It's an online algorithm if you have to make decisions while receiving input. $\endgroup$ – Pål GD Oct 27 '20 at 15:29
  • $\begingroup$ It can be a form of job shop scheduling if you want to have more relaxed criteria. $\endgroup$ – Pål GD Oct 27 '20 at 15:30
  • $\begingroup$ The input can be modeled as an interval graph so try to see if the greedy algorithm works for you (hint: you might need to sort by the endpoint). $\endgroup$ – Pål GD Oct 27 '20 at 15:34
  • $\begingroup$ Thank you for your helpful comments $\endgroup$ – Mohammad Ali Nematollahi Oct 27 '20 at 16:04

The problem can be solved in $O(n \log n)$ time where $n$ is the number of clients (Note that in the trivial case where $k > n$, you simply serve all clients as soon as they come.)

The algorithm is well-known: Sort the intervals by startpoint, endpoint.

Then you iterate over the intervals, for each minute.

If you are at a point where more than $k$ intervals end the next minute, you cannot solve it.

Otherwise you remove the $k$ first intervals in your list, and increase the minute counter.

Note that to be truly polynomial, you might need to skip further ahead than to the next minute, but that's an exercise. (E.g. when the input is $$\left[(2^0, 2^1), (2^2, 2^3), (2^4, 2^5), ..., (2^{100}, 2^{101})\right]$$ or other large numbers.)

  • $\begingroup$ What does "Sort the intervals by startpoint, endpoint" mean? I think you only need to sort them by endpoint here, always taking the up to $k$ earliest-finishing intervals that have already started by the current time. $\endgroup$ – j_random_hacker Oct 27 '20 at 18:28
  • $\begingroup$ @j_random_hacker yes, but to find [those] that have already started you need to find them. Suppose that they all end at the same time. If every interval ends at the same time, the optimal solution is to pick them off by "startpoint". $\endgroup$ – Pål GD Oct 27 '20 at 19:06
  • $\begingroup$ Would it be accurate to say that a list of all $2n$ startpoints and endpoints of the $n$ intervals should be formed, and then sorted? $\endgroup$ – j_random_hacker Oct 28 '20 at 4:07
  • $\begingroup$ Actually, if you are familiar with Python, you simply sort the list of tuples, like this: sorted([(2, 3), (2, 5), (3, 4), (3, 5), (1, 6), (2, 4)]) and that will give you what you need. $\endgroup$ – Pål GD Oct 28 '20 at 7:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.