修车的最少时间

标签: 数组 二分查找

难度: Medium

给你一个整数数组 ranks ，表示一些机械工的 能力值 。ranksi 是第 i 位机械工的能力值。能力值为 r 的机械工可以在 r * n2 分钟内修好 n 辆车。

同时给你一个整数 cars ，表示总共需要修理的汽车数目。

请你返回修理所有汽车 最少 需要多少时间。

注意：所有机械工可以同时修理汽车。

示例 1：

输入：ranks = [4,2,3,1], cars = 10
输出：16
解释：
- 第一位机械工修 2 辆车，需要 4 * 2 * 2 = 16 分钟。
- 第二位机械工修 2 辆车，需要 2 * 2 * 2 = 8 分钟。
- 第三位机械工修 2 辆车，需要 3 * 2 * 2 = 12 分钟。
- 第四位机械工修 4 辆车，需要 1 * 4 * 4 = 16 分钟。
16 分钟是修理完所有车需要的最少时间。

示例 2：

输入：ranks = [5,1,8], cars = 6
输出：16
解释：
- 第一位机械工修 1 辆车，需要 5 * 1 * 1 = 5 分钟。
- 第二位机械工修 4 辆车，需要 1 * 4 * 4 = 16 分钟。
- 第三位机械工修 1 辆车，需要 8 * 1 * 1 = 8 分钟。
16 分钟时修理完所有车需要的最少时间。

提示：

  • 1 <= ranks.length <= 105
  • 1 <= ranks[i] <= 100
  • 1 <= cars <= 106

Submission

运行时间: 63 ms

内存: 19.8 MB

class Solution:
    def repairCars(self, ranks: List[int], cars: int) -> int:
        cnt = Counter(ranks)
        left = 0
        right = min(cnt) * cars * cars
        while left < right:
            mid = left + right >> 1
            if sum(isqrt(mid // r) * c for r, c in cnt.items()) < cars:
                left = mid + 1
            else:
                right = mid
        return right

Explain

这个题解使用了二分搜索的方法来计算最少时间。首先，题目的目标是找到修理所有汽车的最少时间。时间是由机械工的能力值和他们修理的汽车数量决定的。二分搜索的范围设定为从0到最小能力值乘以汽车数的平方（即最坏情况下单个工人修所有车的时间）。在每次迭代中，通过检查当前中间值（mid）时间内是否可以修理完全部汽车来逐步缩小搜索范围。如果在给定的mid时间内所有机械工的总修车数达不到所需汽车数，说明需要更多时间，因此调整搜索范围的左边界。反之，则调整右边界。重复此过程直到找到最小的可行时间。

时间复杂度: O(u * log(maxTime))

空间复杂度: O(u)


python
from collections import Counter
from math import isqrt

class Solution:
    def repairCars(self, ranks: List[int], cars: int) -> int:
        cnt = Counter(ranks)  # 统计每个能力值的机械工数量
        left = 0  # 二分搜索的左边界
        right = min(cnt) * cars * cars  # 二分搜索的右边界，基于最慢的工人单独修所有车的情况
        while left < right:
            mid = (left + right) // 2  # 中间值
            if sum(isqrt(mid // r) * c for r, c in cnt.items()) < cars:  # 计算在mid时间内能修理的总车数
                left = mid + 1  # 不足够，需要更多时间
            else:
                right = mid  # 足够或者有多余，尝试减少时间
        return right  # 返回最小需要时间

Explore

二分搜索是一种高效的搜索方法，适用于在有序的解空间中查找特定值。在这个问题中，最少时间是有序的，即如果在某个时间内能修完所有汽车，那么在更长的时间内也一定能修完。因此，通过二分搜索可以有效地缩小可能的时间范围，从而快速找到最小的符合条件的时间。这种方法比穷举所有可能的时间要高效得多。

右边界 `right = min(cnt) * cars * cars` 是基于最坏情况来设定的，即假设最慢的工人（能力值最低）单独修理所有车辆所需要的最长时间。这个计算假设每个工人在完全不重叠的情况下独立完成修车任务。尽管这个估计很保守，但它确保了二分搜索的上界足够大，能包含实际的最小时间，从而保证搜索的完整性和正确性。

在所有工人能力值相同的情况下，这种方法非常高效，因为所有工人的贡献相同，容易计算出每个时间点下的修车总量，从而快速缩小搜索范围找到最优解。在能力值极度不均匀的情况下，虽然会增加计算每个时间点的修车总量的复杂度，但二分搜索本身仍然有效，能够处理这种不均匀性，逐步逼近最小所需时间。尽管在计算过程中可能会有更多的迭代，但整体上仍然比直接计算每个可能时间要高效。