What is the best strategy to find the minimum repair time for cars?

Use binary search over the valid time range and check for each candidate whether all cars can be repaired by the available mechanics.

How do mechanic ranks affect the total repair time?

Higher-ranked mechanics can repair more cars faster, so their assignment significantly reduces the total time in the binary search feasibility check.

Can the binary search approach fail for large arrays?

It remains efficient as long as calculations for maximum cars per mechanic avoid overflow and use integer arithmetic.

Why use sqrt(t / r) in computing cars per mechanic?

Because a mechanic with rank r takes r * n^2 minutes to repair n cars, solving for n gives floor(sqrt(t / r)) as the maximum number of cars in time t.

Does this problem fit any known algorithm pattern?

Yes, it is a classic binary search over the valid answer space pattern applied to arrays with a quadratic time formula.

#2594

Medium

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

LeetCode 题解工作台

修车的最少时间

给你一个整数数组 ranks ，表示一些机械工的能力值。 ranks i 是第 i 位机械工的能力值。能力值为 r 的机械工可以在 r * n 2 分钟内修好 n 辆车。同时给你一个整数 cars ，表示总共需要修理的汽车数目。请你返回修理所有汽车最少需要多少时间。注意：所有机械工可…

数组二分查找

题目描述

给你一个整数数组 ranks ，表示一些机械工的 能力值 。ranks_i 是第 i 位机械工的能力值。能力值为 r 的机械工可以在 r * n² 分钟内修好 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 <= 10⁵
1 <= ranks[i] <= 100
1 <= cars <= 10⁶

lightbulb

解题思路

方法一：二分查找

我们注意到，修车时间越长，修理的汽车数目也越多。因此，我们可以将修车时间作为二分查找的目标，二分查找修车时间的最小值。

我们定义二分查找的左右边界分别为 $left=0$ , $right=ranks[0] \times cars \times cars$ 。接下来二分枚举修车时间 $mid$ ，每个机械工可以修理的汽车数目为 $\lfloor \sqrt{\frac{mid}{r}} \rfloor$ ，其中 $\lfloor x \rfloor$ 表示向下取整。如果修理的汽车数目大于等于 $cars$ ，则说明修车时间 $mid$ 可行，我们将右边界缩小至 $mid$ ，否则将左边界增大至 $mid+1$ 。

最终，我们返回左边界即可。

时间复杂度 $(n \times \log M)$ ，空间复杂度 $O(1)$ 。其中 $n$ 为机械工的数量，而 $M$ 为二分查找的上界。

1

2

3

4

5

6

7

class Solution:
    def repairCars(self, ranks: List[int], cars: int) -> int:
        def check(t: int) -> bool:
            return sum(int(sqrt(t // r)) for r in ranks) >= cars

        return bisect_left(range(ranks[0] * cars * cars), True, key=check)

speed

复杂度分析

指标	值
时间	O(n + m \log k)
空间	O(k)

psychology

面试官常问的追问

外企场景

question_mark
Focus on binary search over valid answer space rather than greedy car assignment.
question_mark
Consider integer overflow when computing t / r and sqrt values.
question_mark
Check edge cases with few mechanics or a single car to verify correctness.

warning

常见陷阱

外企场景

error
Assigning cars greedily without considering the time-based constraint can produce incorrect minimal times.
error
Miscomputing the number of cars a mechanic can handle in given time by forgetting the square in r * n^2.
error
Failing to account for all mechanics in feasibility check, leading to underestimating repair time.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Modify the problem so each mechanic has a maximum number of cars they can repair, adding a constraint to the binary search feasibility check.
arrow_right_alt
Change the formula to r * n^p for a different exponent p to test adaptability of the binary search pattern.
arrow_right_alt
Include repair speed upgrades for mechanics that reduce their effective rank temporarily, requiring dynamic feasibility calculations.

help

常见问题

外企场景

继续练习

#2589 完成所有任务的最少时间 #2601 质数减法运算 #2602 使数组元素全部相等的最少操作次数