高效的出租车调度

Question

我在准备时遇到了这个技术问题。有K辆出租车。第一辆出租车需要 ki 分钟才能完成任何行程。用这 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

Answer 1

二分查找看起来非常直观和简单。让我们重新定义这个问题：

给定时间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或更多行程的最小值作为输出，这可以在 中完成O(KlogW)，其中W是t我们必须考虑的所有范围。