2594. 修车的最少时间 Medium

给你一个整数数组 ranks ，表示一些机械工的 能力值 。ranks[i] 是第 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 分钟时修理完所有车需要的最少时间。

解题思路

输入： 一个整数数组 ranks, 一个整数 cars

输出： 返回修理所有汽车最少需要的分钟数

本题属于二分答案类问题。

在时间 t 内，我们总共可以修理 sqrt(t // ranks[i]) 辆车

我们需要写一个 check 函数来判断在时间 t 内，可以修理的车辆 >= cars

• 左边界（最小时间）：至少需要 1 分钟
• 右边界（最大时间）：最多需要 min(ranks) * (cars ** 2) （如果最慢的人修理所有车）

最后在左右边界内通过二分法找到最小的满足条件的值

代码实现

python

class Solution:
    def repairCars(self, ranks: List[int], cars: int) -> int:
        # 定义检查函数，判断在时间 t 内是否能修完 cars 辆车
        def can_repair_in_time(t: int) -> bool:
            total = 0
            # 对每个技师的效率 r，计算在时间 t 内能修的车辆数
            for r in ranks:
                # 公式：sqrt(t // r) 表示技师 r 在 t 时间内修的车数
                total += int((t // r) ** 0.5)
            # 返回是否修的车数达到或超过目标
            return total >= cars
        
        # 初始化二分查找的左右边界
        # 左边界为 1（最小时间），右边界为最慢技师修 cars 辆车所需时间
        left, right = 1, min(ranks) * (cars ** 2)
        # 初始化答案为右边界（最大可能时间）
        min_time = right

        # 二分查找寻找最小时间
        while left <= right:
            mid = (left + right) // 2  # 取中间时间点

            # 如果在 mid 时间内能修完所有车
            if can_repair_in_time(mid):
                min_time = mid  # 更新答案为当前时间
                right = mid - 1  # 尝试更短的时间
            else:
                left = mid + 1  # 需要更长的时间
        
        return min_time

javascript

/**
 * @param {number[]} ranks
 * @param {number} cars
 * @return {number}
 */
var repairCars = function(ranks, cars) {
    function check(time) {
        let total = 0;

        for (let r of ranks) {
            total += Math.sqrt(Math.floor(time / r)) | 0;
        }

        return total >= cars;
    }

    let left = 1;
    let right = Math.min(...ranks) * (cars ** 2);
    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(nlog n)

空间复杂度：O(1)

链接

2594 国际版

2594 中文版