526互联

[LeetCode] 2594. Minimum Time to Repair Cars

发布时间 2023-09-07 06:37:06作者: CNoodle

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.

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

修车的最少时间。

给你一个整数数组 ranks ，表示一些机械工的 能力值 。ranksi 是第 i 位机械工的能力值。能力值为 r 的机械工可以在 r * n2 分钟内修好 n 辆车。

同时给你一个整数 cars ，表示总共需要修理的汽车数目。

请你返回修理所有汽车 最少 需要多少时间。

注意：所有机械工可以同时修理汽车。

思路是二分法，且这道题是在答案上二分的类型。

注意题目的定义，ranks 的定义是每位机械工的能力值，ranks[i] 越小，说明他的能力值越小，干活速度越慢。这个和平常我们对 rank 排名的理解是恰恰相反的。我们二分的下界是 0，就是干活速度接近于 0，二分的上界就是 rank 值最小的这名机械工的速度。这里我觉得是需要一些数学推导的，我参考了这个帖子。既然找到了二分的上界和下界，其余的部分就很容易了。

时间O(logn)

空间O(1)

Java实现

 1 class Solution {
 2     public long repairCars(int[] ranks, int cars) {
 3         int min = Integer.MAX_VALUE;
 4         for (int rank : ranks) {
 5             min = Math.min(min, rank);
 6         }
 7 
 8         long left = 0;
 9         long right = (long) min * cars * cars;
10         while (left < right) {
11             long mid = left + (right - left) / 2;
12             long sum = 0;
13             for (int rank : ranks) {
14                 sum += Math.sqrt(mid / rank);
15             }
16             if (sum >= cars) {
17                 right = mid;
18             } else {
19                 left = mid + 1;
20             }
21         }
22         return right;
23     }
24 }

 

LeetCode 题目总结