Problem

You are given an integer array ranks representing the ranks of some mechanics. ranksi is the rank of the ith mechanic. A mechanic with a rank r can repair n cars in r * n2 minutes.

You are also given an integer cars representing the total number of cars waiting in the garage to be repaired.

Return the minimum time taken to repair all the cars.

Note: All the mechanics can repair the cars simultaneously.

Examples

Example 1:

1
2
3
4
5
6
7
8

Input: ranks = [4,2,3,1], cars = 10
Output: 16
Explanation: 
- 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:

1
2
3
4
5
6
7

Input: ranks = [5,1,8], cars = 6
Output: 16
Explanation: 
- 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

Method 1 - Using Binary Search

Here is the approach:

  1. Binary Search for Time:

    • Start with an initial range of possible times: from 1 to cars² * min(rank) (worst case).
    • Check if it is feasible to repair all cars within a given time t.

  2. Feasibility Check:

    • For each mechanic with rank r, calculate the maximum number of cars they can repair within the given time using the formula: rep_cars = sqrt(t / r)
    • Sum up the cars repaired by all mechanics. If the total is greater than or equal to cars, it is feasible to complete all repairs within t.

  3. Iterate:

    • Use binary search to narrow down the minimum time by checking feasibility iteratively.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {
    public long repairCars(int[] ranks, int cars) {
        long left = 1;
        long right = (long) cars * cars * Arrays.stream(ranks).min().getAsInt();
        long ans = right;

        while (left <= right) {
            long mid = left + (right - left) / 2;
            if (canRepairWithinTime(ranks, cars, mid)) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        return ans;
    }

    private boolean canRepairWithinTime(int[] ranks, int cars, long time) {
        long repaired = 0;
        for (int r : ranks) {
            repaired += (long) Math.sqrt(time / r);
            if (repaired >= cars) return true; // Early exit
        }
        return repaired >= cars;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution:
    def repairCars(self, ranks: List[int], cars: int) -> int:
        left, right = 1, cars * cars * min(ranks)
        ans = right

        while left <= right:
            mid = (left + right) // 2
            if self._can_repair_within_time(ranks, cars, mid):
                ans = mid
                right = mid - 1
            else:
                left = mid + 1
        
        return ans

    def _can_repair_within_time(self, ranks: List[int], cars: int, time: int) -> bool:
        rep_cars = 0
        for r in ranks:
            rep_cars += int(math.sqrt(time // r))
            if rep_cars >= cars:  # Early exit
                return True
        return rep_cars >= cars

Complexity

  • ⏰ Time complexity: O(n * log(c^2 * m)) where n is length of ranks, c is cars and m is minimum rank
    • Binary search will have log(cars² * min(rank)) iterations.
    • For each iteration, we check feasibility by iterating over all mechanics, so this takes O(len(ranks)).
  • 🧺 Space complexity: O(1)