#2594

Medium

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Minimum Time to Repair Cars

Find the minimum time to repair all cars using mechanics with different ranks, applying binary search over possible times efficiently.

array binary search

Problem Statement

You are given an integer array ranks where ranks[i] represents the rank of the i-th mechanic. A mechanic with rank r can repair n cars in r * n^2 minutes. You are also given an integer cars representing the total number of cars that need repair.

Return the minimum total time required to repair all cars using any assignment of cars to mechanics. You must optimize to ensure no mechanic is over-assigned and the time is minimized using a binary search approach over possible total times.

Examples

Example 1

Input: ranks = [4,2,3,1], cars = 10

Output: 16

The first mechanic will repair two cars. The time required is 4 * 2 * 2 = 16 minutes.
The second mechanic will repair two cars. The time required is 2 * 2 * 2 = 8 minutes.
The third mechanic will repair two cars. The time required is 3 * 2 * 2 = 12 minutes.
The fourth mechanic will repair four cars. The time required is 1 * 4 * 4 = 16 minutes. It can be proved that the cars cannot be repaired in less than 16 minutes.

Example 2

Input: ranks = [5,1,8], cars = 6

Output: 16

The first mechanic will repair one car. The time required is 5 * 1 * 1 = 5 minutes.
The second mechanic will repair four cars. The time required is 1 * 4 * 4 = 16 minutes.
The third mechanic will repair one car. The time required is 8 * 1 * 1 = 8 minutes. It can be proved that the cars cannot be repaired in less than 16 minutes.

Constraints

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

Solution Approach

Use Binary Search on Time

Treat time as the search space and perform binary search to find the minimum total time. For a candidate time, determine if all cars can be repaired by summing the maximum cars each mechanic can handle within that time.

Calculate Cars per Mechanic

For each mechanic with rank r, the maximum number of cars they can repair in t minutes is floor(sqrt(t / r)). Sum these values across all mechanics to check if at least the required number of cars can be repaired.

Optimize Assignments

Assign cars starting with higher-ranked mechanics to reduce total time. Update the binary search bounds based on feasibility and iterate until the minimal valid time is found.

Complexity Analysis

Metric	Value
Time	O(n + m \log k)
Space	O(k)

The solution iterates over n mechanics and uses binary search over the range of possible times up to k. Time complexity is O(n + m log k) where n is the number of mechanics, m is the number of binary search iterations, and k is the maximum possible time. Space complexity is O(k) for tracking calculations per time check.

What Interviewers Usually Probe

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

Common Pitfalls or Variants

Common pitfalls

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

Follow-up variants

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

FAQ

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.

terminal

Solution

Solution 1: Binary Search

We notice that the longer the repair time, the more cars are repaired. Therefore, we can use the repair time as the target of binary search, and binary search for the minimum repair time.

1

2

3

4

5

6

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)

Continue Practicing

#2589 minimum time to complete all tasks #2601 prime subtraction operation #2602 minimum operations to make all array elements equal