2594. 修车的最少时间

🟠   🔖  数组 二分查找  🔗 力扣 LeetCode

题目

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 <= 10^5
• 1 <= ranks[i] <= 100
• 1 <= cars <= 10^6

题目大意

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

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

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

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

示例 1：

输入： ranks = [4,2,3,1], cars = 10

输出： 16

解释：

• 第一位机械工修 2 辆车，需要 4 * 2 * 2 = 16 分钟。
• 第二位机械工修 2 辆车，需要 2 * 2 * 2 = 8 分钟。
• 第三位机械工修 2 辆车，需要 3 * 2 * 2 = 12 分钟。
• 第四位机械工修 4 辆车，需要 1 * 4 * 4 = 16 分钟。

16 分钟是修理完所有车需要的最少时间。

示例 2：

输入： ranks = [5,1,8], cars = 6

输出： 16

解释：

• 第一位机械工修 1 辆车，需要 5 * 1 * 1 = 5 分钟。
• 第二位机械工修 4 辆车，需要 1 * 4 * 4 = 16 分钟。
• 第三位机械工修 1 辆车，需要 8 * 1 * 1 = 8 分钟。

16 分钟时修理完所有车需要的最少时间。

提示：

• 1 <= ranks.length <= 10^5
• 1 <= ranks[i] <= 100
• 1 <= cars <= 10^6

解题思路

1. 确定搜索范围：

   • 我们需要找到修 cars 辆车所需的最短时间 time。
   • 最小时间 left = 1，即理论上最快的情况下一辆车修理只需要 1 分钟。
   • 最大时间 right = min(ranks) * cars²，即假设只有最快的工人来修所有的车。

2. 二分查找 mid = (left + right) / 2，表示尝试以 mid 作为修 cars 辆车的最短可行时间：

   • 检查是否能在 mid 时间内修完 cars 辆车：
     • 遍历所有 ranks，计算每个工人在 mid 时间内最多能修的车辆数 x = floor(sqrt(mid / rank))。
     • 累加所有工人的修车数量 count，如果 count ≥ cars，说明 mid 可行。
   • 若 mid 可行，尝试更小的 mid，调整 right = mid - 1。
   • 若 mid 不可行，尝试更大的 mid，调整 left = mid + 1。

3. 最终返回最小可行的 mid。

复杂度分析

• 时间复杂度：O(n log T)

  • 二分查找 O(log T)，其中 T = min(ranks) * cars²。
  • 每次 canFixed(time) 遍历 ranks 计算最多能修的车数，时间复杂度 O(n)。
  • 总体复杂度 O(n log T)。

• 空间复杂度：O(1)，仅使用常数额外空间。

代码

/**
 * @param {number[]} ranks
 * @param {number} cars
 * @return {number}
 */
var repairCars = function (ranks, cars) {
	let freqs = new Map();

	for (let rank of ranks) {
		freqs.set(rank, (freqs.get(rank) || 0) + 1);
	}

	const canFixed = (time) => {
		let count = 0;
		for (let [rank, freq] of freqs) {
			count += freq * Math.floor(Math.sqrt(time / rank));
			if (count >= cars) return true;
		}
		return false;
	};

	let left = 1,
		right = Math.min(...ranks) * cars * cars;
	let res;
	while (left <= right) {
		const mid = Math.floor((left + right) / 2);
		if (canFixed(mid)) {
			res = mid;
			right = mid - 1;
		} else {
			left = mid + 1;
		}
	}
	return res;
};

相关题目

题号	标题	题解	标签	难度	力扣
360	有序转化数组 🔒		数组 数学 双指针 1+	🟠	🀄️ 🔗
875	爱吃香蕉的珂珂	[✓]	数组 二分查找	🟠	🀄️ 🔗