Serving $k$ customers with bounded time window 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?
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 &gt; 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.)