What is the main pattern used in Minimum Time to Complete Trips?

The problem uses binary search over the valid answer space, treating total time as a search range.

How do I calculate the number of trips completed by all buses in a given time?

Sum floor(time / time[i]) for each bus i to get the total trips completed by that time.

Can this approach handle a single bus with very large totalTrips?

Yes, binary search scales efficiently even when only one bus exists, avoiding direct simulation.

Why not simulate each trip sequentially?

Sequential simulation exceeds time limits for large arrays or high totalTrips, making binary search essential.

What are typical edge cases to watch for?

Single bus, all buses with equal time, and maximum time values near constraints are key edge cases.

#2187

Medium

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

完成旅途的最少时间

给你一个数组 time ，其中 time[i] 表示第 i 辆公交车完成一趟旅途所需要花费的时间。每辆公交车可以连续完成多趟旅途，也就是说，一辆公交车当前旅途完成后，可以立马开始下一趟旅途。每辆公交车独立运行，也就是说可以同时有多辆公交车在运行且互不影响。给你一个整数 tota…

数组二分查找

题目描述

给你一个数组 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 。

提示：

1 <= time.length <= 10⁵
1 <= time[i], totalTrips <= 10⁷

lightbulb

解题思路

方法一：二分查找

我们注意到，如果我们能在 $t$ 时间内至少完成 $totalTrips$ 趟旅途，那么在 $t' > t$ 时间内也能至少完成 $totalTrips$ 趟旅途。因此我们可以使用二分查找的方法来找到最小的 $t$ 。

我们定义二分查找的左边界 $l = 1$ ，右边界 $r = \min(time) \times \textit{totalTrips}$ 。每一次二分查找，我们计算中间值 $\textit{mid} = \frac{l + r}{2}$ ，然后计算在 $\textit{mid}$ 时间内能完成的旅途数目。如果这个数目大于等于 $\textit{totalTrips}$ ，那么我们将右边界缩小到 $\textit{mid}$ ，否则我们将左边界扩大到 $\textit{mid} + 1$ 。

最后返回左边界即可。

时间复杂度 $O(n \times \log(m \times k))$ ，其中 $n$ 和 $k$ 分别是数组 $time$ 的长度和 $totalTrips$ ，而 $m$ 是数组 $time$ 中的最小值。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

class Solution:
    def minimumTime(self, time: List[int], totalTrips: int) -> int:
        mx = min(time) * totalTrips
        return bisect_left(
            range(mx), totalTrips, key=lambda x: sum(x // v for v in time)
        )

speed

复杂度分析

指标	值
时间	complexity is O(n * log(T)), where n is the number of buses and T is the maximum possible time derived from constraints. Space complexity is O(1) beyond the input array since no extra data structures are needed.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The candidate quickly identifies binary search over the answer space as the key pattern.
question_mark
The candidate demonstrates efficient computation of total trips for a given time.
question_mark
The candidate correctly handles edge cases where buses have varying speeds or only one bus exists.

warning

常见陷阱

外企场景

error
Attempting to simulate each trip sequentially, which exceeds time limits for large arrays.
error
Miscalculating the number of trips by not using integer division.
error
Setting incorrect binary search boundaries that skip the minimum time solution.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Find minimum time for buses with cooldown periods between trips.
arrow_right_alt
Compute minimum time when buses have different start times.
arrow_right_alt
Determine minimum time when only a subset of buses can be active at any moment.

help

常见问题

外企场景

继续练习

#2179 统计数组中好三元组数目 #2226 每个小孩最多能分到多少糖果 #2141 同时运行 N 台电脑的最长时间