修车的最少时间【LC2594】
给你一个整数数组 ranks ，表示一些机械工的 能力值 。ranksi 是第 i 位机械工的能力值。能力值为 r 的机械工可以在 r * n2 分钟内修好 n 辆车。
同时给你一个整数 cars ，表示总共需要修理的汽车数目。
请你返回修理所有汽车 最少 需要多少时间。
**注意：**所有机械工可以同时修理汽车。
class Solution { public long repairCars(int[] ranks, int cars) { long l = 1L; long r = 1L * ranks[0] * cars * cars; while (l <= r){ long mid = l + (r - l) / 2; if (check(ranks, mid, cars)){ r = mid - 1; }else{ l = mid + 1; } } return l; } public boolean check(int[] ranks,long time, int target){ int total = 0; for (int rank : ranks){ total += (int)Math.sqrt(time / rank); if (total >= target){ return true; } } return false; } }
复杂度
时间复杂度：O ( n l o g m )，n是数组的长度，m是二分查找的上界。二分查找的时间复杂度是O (logm) ，每次判断需要的时间复杂度为O ( n )
空间复杂度：O ( 1 )
