2187. 完成旅途的最少时间 Medium
给你一个数组 time ，其中 time[i] 表示第 i 辆公交车完成 一趟旅途 所需要花费的时间。
每辆公交车可以 连续 完成多趟旅途，也就是说，一辆公交车当前旅途完成后，可以 立马开始 下一趟旅途。每辆公交车 独立 运行，也就是说可以同时有多辆公交车在运行且互不影响。
给你一个整数 totalTrips ，表示所有公交车 总共 需要完成的旅途数目。请你返回完成 至少 totalTrips 趟旅途需要花费的 最少 时间。
示例 1:
输入：time = [1,2,3], totalTrips = 5
输出：3
解释：
时刻 t = 1 ，每辆公交车完成的旅途数分别为 [1,0,0] 。
已完成的总旅途数为 1 + 0 + 0 = 1 。
时刻 t = 2 ，每辆公交车完成的旅途数分别为 [2,1,0] 。
已完成的总旅途数为 2 + 1 + 0 = 3 。
时刻 t = 3 ，每辆公交车完成的旅途数分别为 [3,1,1] 。
已完成的总旅途数为 3 + 1 + 1 = 5 。
所以总共完成至少 5 趟旅途的最少时间为 3 。
示例 2:
输入：time = [2], totalTrips = 1
输出：2
解释：
只有一辆公交车，它将在时刻 t = 2 完成第一趟旅途。
所以完成 1 趟旅途的最少时间为 2 。
解题思路
输入： 一个整数数组 time 表示每个公交车完成一趟旅程需要花费的时间
输出： 返回能完成 totalTrips 所需要花费的最小时间
本题属于二分答案类问题，也属于 求最小 问题。
我们需要写一个 check 函数来判断在时间 t 内，每辆车可以跑 t // time[i] 次旅程，相加是否 >= totalTrips
- 左边界（最小时间）：至少需要 1 时间
- 右边界（最大时间）：最多需要
min(time) * totalTrips（如果最快的车一个人干所有活）
最后在左右边界内通过二分法找到最小的满足条件的值
代码实现
class Solution:
def minimumTime(self, time: List[int], totalTrips: int) -> int:
# 定义检查函数：判断在时间 t 内是否能完成至少 totalTrips 次旅行
def check(t):
total = 0
# 遍历每辆公交车的单次旅行时间 ti
for ti in time:
# 计算在时间 t 内，这辆公交车能完成的旅行次数（t // ti）
total += t // ti
# 返回是否满足完成至少 totalTrips 次旅行的条件
return total >= totalTrips
# 初始化二分查找的左右边界
# left = 1（最小可能时间）
# right = min(time) * totalTrips（最大可能时间，假设最快公交车完成所有旅行）
left, right = 1, min(time) * totalTrips
# 初始化答案为 right（最差情况）
ans = right
# 二分查找寻找最小时间
while left <= right:
# 计算中间时间点
mid = (left + right) // 2
# 如果时间 mid 能完成至少 totalTrips 次旅行
if check(mid):
# 记录当前可行解，并尝试更小的时间（缩小右边界）
ans = mid
right = mid - 1
else:
# 如果不能完成，说明时间不够，增大左边界
left = mid + 1
# 返回最小的可行时间
return ans/**
* @param {number[]} time
* @param {number} totalTrips
* @return {number}
*/
var minimumTime = function(time, totalTrips) {
function check(t) {
let total = 0;
for (let ti of time) {
total += Math.floor(t / ti);
}
return total >= totalTrips;
}
let left = 1;
let right = Math.min(...time) * totalTrips;
let ans = right;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (check(mid)) {
ans = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
return ans;
};复杂度分析
时间复杂度：O(log n)
空间复杂度：O(1)