Maximum Running Time of n Computers

Given battery capacities, find the maximum time all n computers can run simultaneously.

binary-search greedy array

You have n computers and a list of batteries. Each computer requires one battery to run. Each battery has a certain amount of energy (an integer). At any time, you can place any battery into any computer. You can swap batteries between computers at any time, and when a battery is drained, it is removed. You cannot charge batteries. If you have more batteries than computers, you can use the extra batteries as replacements when a battery runs out. You want to maximize the total time (an integer number of minutes) that all n computers are running simultaneously.

Write a function `max_run_time(n: int, batteries: list[int]) -> int` that returns the maximum possible running time in minutes. The running time must be an integer: you can only run for whole minutes (use each battery's energy per minute, one minute consumes 1 energy unit).

Note: You can have more batteries than computers. You can swap batteries at any time (including fractional minutes, but the final answer is the maximum integer time). For a given time T, a schedule exists if and only if the sum of min(battery_capacity, T) for all batteries is >= n * T.

Constraints

- 1 <= n <= 10^5
- 1 <= batteries.length <= 10^5
- 1 <= batteries[i] <= 10^9
- The total energy of all batteries is at least n (so at least 1 minute is possible).
- Time complexity expected O(N log M) where N = batteries.length and M = total energy / n.

Example

>>> max_run_time(2, [3, 3, 3])
4
>>> max_run_time(2, [1, 1, 1, 1])
2
>>> max_run_time(1, [5])
5

30 points ~30 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think of a predicate function can_run(T) that checks if all n computers can run for T minutes.

For a given T, each battery can contribute at most T energy units, and if a battery has more than T, the excess is unused for that T.

Binary search on T from 1 to (total_energy // n).

The answer is the maximum T for which sum(min(battery, T)) >= n * T.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.