Minimum Time to Repair Cars

main.md

Question

Approach

I use a binary search approach to determine the minimum time needed to repair all cars. The search range is from 1 to the maximum possible repair time, calculated as min(ranks) * cars^2. The helper function canRepairWithinTime(t) checks if the given time t allows enough cars to be repaired.

Implementation

class Solution:
    def repairCars(self, ranks: List[int], cars: int) -> int:
        left, right = 1, min(ranks) * cars * cars
        
        def canRepairWithinTime(t: int) -> bool:
            total_cars = sum(int((t // r) ** 0.5) for r in ranks)
            return total_cars >= cars
        
        while left < right:
            mid = (left + right) // 2
            if canRepairWithinTime(mid):
                right = mid
            else:
                left = mid + 1
        
        return left

Complexities

• Time: O(n log max_time)
• Space: O(1)