What is the time complexity of the solution for the Maximum Running Time of N Computers?

The time complexity is O(m \cdot\log k), where m is the number of batteries, and k is the total time range.

How does binary search help in solving the Maximum Running Time of N Computers?

Binary search is used to find the maximum possible running time by checking if a given running time is feasible using the available batteries.

Can I use a greedy algorithm alone to solve the Maximum Running Time of N Computers?

A greedy algorithm can help in distributing batteries efficiently, but binary search is necessary to find the optimal running time.

What is the key approach in solving the Maximum Running Time of N Computers?

The key approach is binary search over the possible running times combined with a greedy method for battery distribution.

What are the common pitfalls when solving the Maximum Running Time of N Computers?

Common pitfalls include misunderstanding battery distribution, misapplying binary search bounds, and inefficient battery swapping strategies.

#2141

Hard

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

同时运行 N 台电脑的最长时间

你有 n 台电脑。给你整数 n 和一个下标从 0 开始的整数数组 batteries ，其中第 i 个电池可以让一台电脑运行 batteries[i] 分钟。你想使用这些电池让全部 n 台电脑同时运行。一开始，你可以给每台电脑连接至多一个电池。然后在任意整数时刻，你都可以将一台电脑与它…

数组二分查找贪心排序

题目描述

你有 n 台电脑。给你整数 n 和一个下标从 0 开始的整数数组 batteries ，其中第 i 个电池可以让一台电脑运行 batteries[i] 分钟。你想使用这些电池让全部 n 台电脑同时运行。

一开始，你可以给每台电脑连接 至多一个电池 。然后在任意整数时刻，你都可以将一台电脑与它的电池断开连接，并连接另一个电池，你可以进行这个操作 任意次 。新连接的电池可以是一个全新的电池，也可以是别的电脑用过的电池。断开连接和连接新的电池不会花费任何时间。

注意，你不能给电池充电。

请你返回你可以让 n 台电脑同时运行的最长分钟数。

示例 1：

输入：n = 2, batteries = [3,3,3]
输出：4
解释：
一开始，将第一台电脑与电池 0 连接，第二台电脑与电池 1 连接。
2 分钟后，将第二台电脑与电池 1 断开连接，并连接电池 2 。注意，电池 0 还可以供电 1 分钟。
在第 3 分钟结尾，你需要将第一台电脑与电池 0 断开连接，然后连接电池 1 。
在第 4 分钟结尾，电池 1 也被耗尽，第一台电脑无法继续运行。
我们最多能同时让两台电脑同时运行 4 分钟，所以我们返回 4 。

示例 2：

输入：n = 2, batteries = [1,1,1,1]
输出：2
解释：
一开始，将第一台电脑与电池 0 连接，第二台电脑与电池 2 连接。
一分钟后，电池 0 和电池 2 同时耗尽，所以你需要将它们断开连接，并将电池 1 和第一台电脑连接，电池 3 和第二台电脑连接。
1 分钟后，电池 1 和电池 3 也耗尽了，所以两台电脑都无法继续运行。
我们最多能让两台电脑同时运行 2 分钟，所以我们返回 2 。

提示：

1 <= n <= batteries.length <= 10⁵
1 <= batteries[i] <= 10⁹

lightbulb

解题思路

方法一：二分查找

我们注意到，如果我们可以让 $n$ 台电脑同时运行 $t$ 分钟，那么我们也可以让 $n$ 台电脑同时运行 $t' \le t$ 分钟，这存在着单调性。因此，我们可以使用二分查找的方法找到最大的 $t$ 。

我们定义二分查找的左边界 $l=0$ ，右边界 $r=\sum_{i=0}^{n-1} batteries[i]$ 。每次二分查找的过程中，我们使用一个变量 $mid$ 表示当前的中间值，即 $mid = (l + r + 1) >> 1$ 。我们判断是否存在一种方案，使得 $n$ 台电脑同时运行 $mid$ 分钟。如果存在，那么我们就将 $l$ 更新为 $mid$ ，否则我们将 $r$ 更新为 $mid - 1$ 。最后，我们返回 $l$ 即为答案。

问题转化为如何判断是否存在一种方案，使得 $n$ 台电脑同时运行 $mid$ 分钟。如果一个电池可以运行的分钟数大于 $mid$ ，由于电脑同时运行 $mid$ 分钟，而一个电池同一时间只能供电一台电脑，因此我们只能使用这个电池 $mid$ 分钟。如果一个电池可以运行的分钟数小于等于 $mid$ ，我们可以使用这个电池的全部电量。因此，我们统计所有电池可以供电的分钟数之和 $s$ ，如果 $s \ge n \times mid$ ，那么我们就可以使得 $n$ 台电脑同时运行 $mid$ 分钟。

时间复杂度 $O(n \times \log M)$ ，其中 $M$ 为所有电池的电量之和，空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def maxRunTime(self, n: int, batteries: List[int]) -> int:
        l, r = 0, sum(batteries)
        while l < r:
            mid = (l + r + 1) >> 1
            if sum(min(x, mid) for x in batteries) >= n * mid:
                l = mid
            else:
                r = mid - 1
        return l

speed

复杂度分析

指标	值
时间	O(m \cdot\log k)
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Check if the candidate understands binary search applied to a valid answer space.
question_mark
Look for the candidate’s approach to checking the feasibility of each running time in the binary search range.
question_mark
Assess how the candidate balances the greedy algorithm with the binary search approach.

warning

常见陷阱

外企场景

error
Misunderstanding the battery distribution logic: ensuring all batteries are used efficiently is key.
error
Overcomplicating the binary search bounds: the search range is simply between 0 and the total sum of battery times.
error
Failing to correctly swap batteries between computers at optimal moments, leading to inefficient running times.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Varying the number of computers n, keeping battery count the same.
arrow_right_alt
Varying the distribution of battery times: very large vs small battery times.
arrow_right_alt
Introducing constraints where batteries can only be swapped a limited number of times.

help

常见问题

外企场景

继续练习

#2071 你可以安排的最多任务数目 #2234 花园的最大总美丽值 #2271 毯子覆盖的最多白色砖块数