It is possible to implement a solution that, for each person, computes (fast enough) the desk where the person will finish check-in soonest. It can be done using, for example, a priority_queue structure; details are left as an exercise to the reader. Such a solution has a complexity of ~\mathcal O(M \log N)~. Notice that this greedy solution is also optimal: if every person selects a desk that is optimal for them, it is possible to order all of them in such a way that they don't have to pointlessly wait for one another, leading to such behaviour being optimal for the whole team. Consider why that is correct.

In any case, the solution above isn't fast enough for ~M = 1\,000\,000\,000~. A solution that is fast enough, with complexity ~\mathcal O(N \log M)~, uses binary search: we need to find the earliest time in which the whole team can finish check-in, which requires being able to tell, for any time ~T~, whether it is smaller or larger than the optimum – whether ~M~ people can finish check-in in time ~T~ or not.

How can we check that? For each desk ~k~, we compute how many people that desk can process in time ~T~ (which is ~T \mathbin{div} T_k~), and compute the sum of the obtained numbers. If the sum is greater than or equal to ~M~, it is possible to process ~M~ people (under the assumption that they select desks using a sufficiently smart strategy); otherwise, it is obviously impossible.

The algorithm should be clear now: we keep an upper and lower binary search bound, select a number ~T~ which is the average of the two bounds, determine (as described above) whether it is larger or smaller than the optimal solution and, based on that, move the upper or lower bound to ~T~, halving the interval of potential solutions until only one number remains.