准时到达的列车最小时速

难度: Medium

给你一个浮点数 hour ，表示你到达办公室可用的总通勤时间。要到达办公室，你必须按给定次序乘坐 n 趟列车。另给你一个长度为 n 的整数数组 dist ，其中 dist[i] 表示第 i 趟列车的行驶距离（单位是千米）。

每趟列车均只能在整点发车，所以你可能需要在两趟列车之间等待一段时间。

例如，第 1 趟列车需要 1.5 小时，那你必须再等待 0.5 小时，搭乘在第 2 小时发车的第 2 趟列车。

返回能满足你准时到达办公室所要求全部列车的 最小正整数 时速（单位：千米每小时），如果无法准时到达，则返回 -1 。

生成的测试用例保证答案不超过 10⁷ ，且 hour 的 小数点后最多存在两位数字 。

示例 1：

输入：dist = [1,3,2], hour = 6
输出：1
解释：速度为 1 时：
- 第 1 趟列车运行需要 1/1 = 1 小时。
- 由于是在整数时间到达，可以立即换乘在第 1 小时发车的列车。第 2 趟列车运行需要 3/1 = 3 小时。
- 由于是在整数时间到达，可以立即换乘在第 4 小时发车的列车。第 3 趟列车运行需要 2/1 = 2 小时。
- 你将会恰好在第 6 小时到达。

示例 2：

输入：dist = [1,3,2], hour = 2.7
输出：3
解释：速度为 3 时：
- 第 1 趟列车运行需要 1/3 = 0.33333 小时。
- 由于不是在整数时间到达，故需要等待至第 1 小时才能搭乘列车。第 2 趟列车运行需要 3/3 = 1 小时。
- 由于是在整数时间到达，可以立即换乘在第 2 小时发车的列车。第 3 趟列车运行需要 2/3 = 0.66667 小时。
- 你将会在第 2.66667 小时到达。

示例 3：

输入：dist = [1,3,2], hour = 1.9
输出：-1
解释：不可能准时到达，因为第 3 趟列车最早是在第 2 小时发车。

提示：

n == dist.length
1 <= n <= 10⁵
1 <= dist[i] <= 10⁵
1 <= hour <= 10⁹
hours 中，小数点后最多存在两位数字

Submission

运行时间: 624 ms

内存: 27.5 MB

class Solution:
    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:
        n = len(dist)
        if hour <= n - 1:
            return -1

        left = 0 # false, speed = 0 一定不可能到
        right = max(max(dist), ceil(dist[-1] / (hour - (n - 1))))  # true, max speed 保证一定能到
        while left + 1 < right:
            mid = (left + right) // 2
            if self.check(dist, mid, hour):
                right = mid
            else:
                left = mid
        return right
    
    def check(self, dist, speed, hour):
        # 速度越小，越不可能arrive on time，所以是xxxyyyy模型， move right
        need = 0
        for d in dist[:-1]:
            need += (d - 1) // speed + 1
        need += dist[-1] / speed
        return need <= hour

Explain

这个题解使用了二分查找的方法来寻找最小的满足条件的时速。首先，如果可用时间小于列车数量减一（即hour <= n - 1），则无法准时到达，返回-1。接着，定义搜索区间的左右边界，左边界设为0（不可能的速度），右边界设为max(dist)和ceil(dist[-1] / (hour - (n - 1)))的较大值，保证这个速度一定能到达。然后，进行二分查找，计算中间值mid，检查以mid为速度是否能准时到达。如果能，说明速度还可以更小，移动右边界；如果不能，说明速度需要增加，移动左边界。最终返回右边界作为结果。

时间复杂度: O(nlog(maxSpeed))

空间复杂度: O(1)

class Solution:
    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:
        n = len(dist)
        if hour <= n - 1:
            return -1

        left = 0
        right = max(max(dist), ceil(dist[-1] / (hour - (n - 1))))
        while left + 1 < right:
            mid = (left + right) // 2
            if self.check(dist, mid, hour):
                right = mid
            else:
                left = mid
        return right
    
    def check(self, dist, speed, hour):
        need = 0
        for d in dist[:-1]:
            need += (d - 1) // speed + 1
        need += dist[-1] / speed
        return need <= hour

Explore

在二分查找中，设置左边界为0虽然0速度不现实，这样做主要是为了简化边界处理。具体到算法实现中，我们并不会真正考虑速度为0的情况，因为在二分查找过程中，实际计算始终从中间值开始，即`mid = (left + right) // 2`，而当左边界为0时，第一个mid一定大于0（只要right初始值大于0）。这种设置简化了代码，避免了对速度为1的特殊处理。

右边界的设定是为了确保所选速度一定能覆盖最极端的情况。考虑两种情况：1) max(dist)确保速度足以在一个单位时间内通过任何单一段的最大距离。2) `ceil(dist[-1] / (hour - (n - 1)))`确保最后一段可以在剩余时间内走完。这个时间是总时间减去前面n-1段至少需要的时间（每段至少需要1小时，不考虑速度）。选择这两者的较大值作为右边界，是为了保证在所有情况下，选择的速度都能满足题目要求，从而使算法的正确性和全面性得到保证。

使用`left + 1 < right`作为循环终止条件是为了避免在循环体内出现死循环，并精确控制搜索范围。当两个边界相邻时（left和right之间的差为1），如果继续使用`left < right`作为条件，有可能导致mid重复计算同一个值，从而陷入无限循环。使用`left + 1 < right`确保了当两个边界相邻时退出循环，这时right指向的值是满足条件的最小速度，这样可以有效地找到解决方案。

即使`need == hour`表明当前速度mid可以准时到达，算法仍需尝试更小的速度，以确保找到‘最小’的满足条件的速度。这是因为题目要求的是‘最小’时速。如果不继续尝试更小的速度，就可能错过更优的解。因此，即使当前mid满足条件，也将右边界移动到mid，继续搜索左半区间，以便探索是否有更小的可行速度。