algorithm - 高效的驾驶室调度

我在准备时遇到了这个技术问题。有K辆出租车。坐出租车要花上几分钟才能完成任何行程。用这些计程车完成N次旅行所需的最少时间是多少？我们可以假设两次旅行之间没有等待时间，不同的出租车可以同时出行。有人能提出有效的算法来解决这个问题吗。
例子：

Input:
N=3 K=2
K1 takes 1 minute, K2 takes 2 minutes

Output:
2 minutes

Explanation: Both cabs starts trip at t=0. At t=1, first cab starts third trip. So by t=2, required 3 trips will be completed

最佳答案

二进制搜索看起来非常直观和简单。让我们重新审视这个问题：
给定时间t，计算可以采取的最大行程次数。
我们可以在O(K)中完成考虑到每个驾驶室i可以在t / k_i时间内达到t行程，我们可以简单地得到每个t / k_i的所有i的总和，以获得在t时间内的最大行程次数。这使我们可以建立一个函数，我们可以二进制搜索：

def f(time):
    n_trips = 0
    for trip_time in cabs:
        n_trips += time // trip_time
    return n_trips

很明显，随着时间的增加，我们可以进行的旅行也会增加，所以f(x)是非减少的，这意味着我们可以对它进行二进制搜索。
我们对最小的t进行了二进制搜索，给出了N或更多的TRIPS作为输出，这可以在O(KlogW)中完成，其中W是所有t的范围，我们必须考虑。

关于algorithm - 高效的驾驶室调度，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/58173398/