Question

2594. Minimum Time to Repair Cars

中文文档

Description

You are given an integer array ranks representing the ranks of some mechanics. ranks_i is the rank of the i^th 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.

 

Example 1:

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:

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

Solutions

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.

We define the left and right boundaries of the binary search as $left=0$, $right=ranks[0] \times cars \times cars$. Next, we binary search for the repair time $mid$, and the number of cars each mechanic can repair is $\lfloor \sqrt{\frac{mid}{r}} \rfloor$, where $\lfloor x \rfloor$ represents rounding down. If the number of cars repaired is greater than or equal to $cars$, it means that the repair time $mid$ is feasible, we reduce the right boundary to $mid$, otherwise we increase the left boundary to $mid+1$.

Finally, we return the left boundary.

The time complexity is $O(n \times \log M)$, and the space complexity is $O(1)$. Here, $n$ is the number of mechanics, and $M$ is the upper bound of the binary search.

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)

class Solution {
  public long repairCars(int[] ranks, int cars) {
    long left = 0, right = 1L * ranks[0] * cars * cars;
    while (left < right) {
      long mid = (left + right) >> 1;
      long cnt = 0;
      for (int r : ranks) {
        cnt += Math.sqrt(mid / r);
      }
      if (cnt >= cars) {
        right = mid;
      } else {
        left = mid + 1;
      }
    }
    return left;
  }
}

class Solution {
public:
  long long repairCars(vector<int>& ranks, int cars) {
    long long left = 0, right = 1LL * ranks[0] * cars * cars;
    while (left < right) {
      long long mid = (left + right) >> 1;
      long long cnt = 0;
      for (int r : ranks) {
        cnt += sqrt(mid / r);
      }
      if (cnt >= cars) {
        right = mid;
      } else {
        left = mid + 1;
      }
    }
    return left;
  }
};

func repairCars(ranks []int, cars int) int64 {
  return int64(sort.Search(ranks[0]*cars*cars, func(t int) bool {
    cnt := 0
    for _, r := range ranks {
      cnt += int(math.Sqrt(float64(t / r)))
    }
    return cnt >= cars
  }))
}

function repairCars(ranks: number[], cars: number): number {
  let left = 0;
  let right = ranks[0] * cars * cars;
  while (left < right) {
    const mid = left + Math.floor((right - left) / 2);
    let cnt = 0;
    for (const r of ranks) {
      cnt += Math.floor(Math.sqrt(mid / r));
    }
    if (cnt >= cars) {
      right = mid;
    } else {
      left = mid + 1;
    }
  }
  return left;
}