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