Solution: Maximum Running Time of N Computers

Statement

You are given an integer, n, representing the number of computers, and a 0-indexed integer array, batteries, where batteries[i] denotes the number of minutes the $i^{th}$ battery can power a computer.

Your goal is to run all n computers simultaneously for the maximum possible number of minutes using the available batteries.

Initially, you may assign at most one battery to each computer. After that, at any moment, you may remove a battery from a computer and replace it with another battery—either an unused battery or one taken from another computer. This replacement process can be repeated any number of times and takes no time.

Each battery can power any computer multiple times, but only until it is completely drained. Batteries cannot be recharged.

Return the maximum number of minutes you can run all n computers simultaneously.

Constraints:

• 1 $\leq$ n $\leq$ batteries.length $\leq$ $10^{5}$

• 1 $\leq$ batteries[i] $\leq$ $10^{5}$

Solution

This solution aims to find the maximum number of minutes all n computers can run simultaneously using a set of batteries. We use a modified binary search pattern on the possible runtime values to achieve this. The key observation is that if it’s possible to run all n computers for x minutes, it is also possible to run them for any time less than x. This monotonic propertyIt is a characteristic of a function where the values either consistently increase or decrease. In simpler words, if one works, all smaller values will also work. makes binary search applicable. To solve this, we set the search space from $0$ to total_power // n, where total_power is the sum of all battery capacities. At each step, we check whether running all computers for mid minutes is feasible by verifying that the sum of the available battery contributions (each battery contributing up to mid minutes) is at least n * mid. This feasibility check helps us efficiently narrow down the maximum achievable runtime.

Now, let’s look at the solution steps below:

1. Set left = 0 and right = sum(batteries) // n to define the minimum and maximum possible simultaneous runtime.

2. While left < right:

   1. Calculate mid = right - (right - left) // 2 (biases the midpoint toward the higher end to avoid infinite loops).

   2. Initialize usable = 0 to store the sum of usable power.

   3. For each battery, add min(b, mid) to usable.

   4. If usable >= mid × n, the target is feasible, so set left = mid to search for a longer time.

   5. Otherwise, set right = mid - 1 to search in the lower half.

3. After the loop completes, left holds the maximum number of minutes that all n computers can run simultaneously.

Let’s look at the following illustration to get a better understanding of the solution: