修车的最少时间

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

/*
 * 思路：与普通Java方法类似，使用二分查找找到最小时间。唯一不同的是，使用Java Stream API来计算车的总数。
 */

import java.util.Arrays;

public class Solution {
    public int repairCars(int[] ranks, int cars) {
        int left = 1;
        int right = 100 * cars * cars;
        while (left < right) {
            int mid = (left + right) / 2;
            if (canRepairAllCars(ranks, cars, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    private boolean canRepairAllCars(int[] ranks, int cars, int time) {
        return Arrays.stream(ranks)
                .mapToDouble(rank -> Math.sqrt(time / (double) rank))
                .sum() >= cars;
    }
}

这个题解使用了二分搜索的方法来计算最少时间。首先，题目的目标是找到修理所有汽车的最少时间。时间是由机械工的能力值和他们修理的汽车数量决定的。二分搜索的范围设定为从0到最小能力值乘以汽车数的平方（即最坏情况下单个工人修所有车的时间）。在每次迭代中，通过检查当前中间值（mid）时间内是否可以修理完全部汽车来逐步缩小搜索范围。如果在给定的mid时间内所有机械工的总修车数达不到所需汽车数，说明需要更多时间，因此调整搜索范围的左边界。反之，则调整右边界。重复此过程直到找到最小的可行时间。

O(u * log(maxTime))

O(u)