LeetCode每日一题解析：同时运行 N 台电脑的最长时间

LeetCode每日一题解析：同时运行 N 台电脑的最长时间

题目链接

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

题目描述

给定一个整数数组 batteries，表示 N 台电脑的电池容量。我们需要计算这 N 台电脑能够同时运行的最长时间。每台电脑的运行时间取决于电池的剩余电量，且电池可以拆分成任意数量的小块来使用。目标是最大化所有电脑的运行时间。

解题思路

为了最大化所有电脑的运行时间，我们需要合理分配电池资源。一个直观的思路是，每过一分钟，将所有电脑连接到电量最多的电池上。然而，这种方法会导致每分钟都需要重新计算，从而可能导致超时。

改进的思路是，将电池按容量降序排列。然后，假设前 N 个电池一直处于充电状态，而剩余的电池则用于补充前 N 个电池的电量。每次补充时，我们尝试将前一个电池的电量补足到当前电池的电量。如果无法补足，则将剩余电量平均分配给前 N 个电池。

代码实现

class Solution {
    public long maxRunTime(int n, int batteries) {
        Arrays.sort(batteries);
        long add = 0;
        int addCnt = batteries.length - n;
        for (int i = 0; i < addCnt; i++) {
            add += batteries[i];
        }
        long ans = batteries[addCnt];
        int idx = addCnt;
        while (true) {
            if (idx == batteries.length - 1) {
                return ans + add / n;
            }
            if ((batteries[idx + 1] - ans) * (idx - addCnt + 1) < add) {
                add -= (batteries[idx + 1] - ans) * (idx - addCnt + 1);
                ans = batteries[idx + 1];
                idx++;
            } else {
                return ans + add / (idx - addCnt + 1);
            }
        }
    }
}

时间复杂度与空间复杂度

• 时间复杂度：O(mlogm)，其中 m 是电池的数量，因为我们需要对电池进行排序。
• 空间复杂度：O(1)，因为我们只使用了常数额外空间。

总结

通过合理分配电池资源，我们可以最大化所有电脑的运行时间。在实现时，我们需要注意电池的排序和电量补充的策略，以确保算法的效率和正确性。