We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Time to Repair Cars

Number: 2665

Difficulty: Medium

Paid? No

Companies: Google, Amazon, Deloitte, Microsoft

Problem Description

Given an array of mechanic ranks and a total number of cars, determine the minimum time required so that all the cars can be repaired. Each mechanic with a rank r repairs n cars in r * n² minutes. All mechanics work simultaneously.

Key Insights

  • Use binary search on time to find the minimal value that satisfies the repair condition.
  • For a given time T, a mechanic with rank r can repair floor(sqrt(T / r)) cars.
  • Sum the repairs for all mechanics to check if they meet or exceed the target number of cars.
  • The search space for time is bounded between 0 and (min(ranks) * cars²).

Space and Time Complexity

Time Complexity: O(n * log(maxTime)) where n is the number of mechanics and maxTime is min(ranks) * cars². Space Complexity: O(1) additional space apart from the input.

Solution

We approach this problem using binary search. We set our initial boundaries as low = 0 and high = (min(ranks) * cars²) since a mechanic with the smallest rank is the fastest and will drive the upper limit in the worst-case scenario.

For each candidate time T in our binary search, we calculate the total number of cars that all mechanics can repair:

  • For each mechanic with rank r, compute floor(sqrt(T / r)).
  • Sum these values; if the sum is at least the target number of cars, then T is feasible.

If T is feasible, we try to find a smaller T by moving the high bound down; otherwise, we increase the low bound. This process continues until we find the minimum T for which the condition holds.

Code Solutions

# Python solution using binary search

def repairCars(ranks, cars):
    # Helper function to determine if all cars can be repaired in 'time' minutes.
    def can_repair(time):
        total = 0
        for rank in ranks:
            # Each mechanic can repair floor(sqrt(time / rank)) cars.
            total += int((time // rank) ** 0.5)
            if total >= cars:
                return True
        return total >= cars

    # Lower bound is 0, upper bound is min(ranks) * (cars²)
    low, high = 0, min(ranks) * cars * cars
    result = high
    
    # Binary search for the minimum time required.
    while low <= high:
        mid = (low + high) // 2
        if can_repair(mid):
            result = mid  # mid is a potential answer.
            high = mid - 1  # Try to find a smaller time.
        else:
            low = mid + 1
    return result

# Example usage:
print(repairCars([4, 2, 3, 1], 10))  # Expected output: 16
← Back to All Questions