Watch 10 video solutions for Maximum Running Time of N Computers, a hard level problem involving Array, Binary Search, Greedy. This walkthrough by codestorywithMIK has 13,646 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You have n computers. You are given the integer n and a 0-indexed integer array batteries where the ith battery can run a computer for batteries[i] minutes. You are interested in running all n computers simultaneously using the given batteries.
Initially, you can insert at most one battery into each computer. After that and at any integer time moment, you can remove a battery from a computer and insert another battery any number of times. The inserted battery can be a totally new battery or a battery from another computer. You may assume that the removing and inserting processes take no time.
Note that the batteries cannot be recharged.
Return the maximum number of minutes you can run all the n computers simultaneously.
Example 1:
Input: n = 2, batteries = [3,3,3] Output: 4 Explanation: Initially, insert battery 0 into the first computer and battery 1 into the second computer. After two minutes, remove battery 1 from the second computer and insert battery 2 instead. Note that battery 1 can still run for one minute. At the end of the third minute, battery 0 is drained, and you need to remove it from the first computer and insert battery 1 instead. By the end of the fourth minute, battery 1 is also drained, and the first computer is no longer running. We can run the two computers simultaneously for at most 4 minutes, so we return 4.
Example 2:
Input: n = 2, batteries = [1,1,1,1] Output: 2 Explanation: Initially, insert battery 0 into the first computer and battery 2 into the second computer. After one minute, battery 0 and battery 2 are drained so you need to remove them and insert battery 1 into the first computer and battery 3 into the second computer. After another minute, battery 1 and battery 3 are also drained so the first and second computers are no longer running. We can run the two computers simultaneously for at most 2 minutes, so we return 2.
Constraints:
1 <= n <= batteries.length <= 1051 <= batteries[i] <= 109Problem Overview: You have n computers and a list of battery capacities. A computer can run on any battery, and batteries can be swapped between computers at any time. The goal is to compute the maximum number of minutes all n computers can run simultaneously.
Approach 1: Greedy with Sorting (O(m log m) time, O(1) space)
Start by sorting the battery capacities using sorting. If a battery is extremely large compared to others, dedicating it to a single computer wastes potential shared runtime. The greedy idea is to treat total battery energy as a shared pool while gradually eliminating oversized batteries that exceed the average runtime. Compute the total sum of all capacities, then compare the largest battery with sum / n. If the largest battery is bigger than the average share, remove it from the pool and reduce the number of computers considered. Continue until the largest battery fits within the equal distribution. The remaining average sum / n becomes the maximum running time. Sorting makes it easy to process the largest batteries first, and the greedy reasoning works because runtime is limited by how evenly total energy can be distributed.
Approach 2: Binary Search on Maximum Time (O(m log S) time, O(1) space)
This approach treats the runtime as the value to search for using binary search. The key observation: if you guess a runtime t, each battery can contribute at most min(capacity, t) minutes because a single battery cannot power multiple computers simultaneously beyond its capacity. Sum these contributions across all batteries. If the total available minutes is at least n * t, then running all computers for t minutes is feasible.
Binary search between 0 and sum(batteries) / n. For each candidate time, iterate through the array of batteries and accumulate min(battery, t). If the sum meets the requirement, move the search right to try a larger runtime; otherwise move left. This feasibility check forms a classic "search on answer" pattern. The approach combines greedy resource allocation with binary search to efficiently handle large inputs.
Recommended for interviews: The binary search solution is what most interviewers expect. It demonstrates recognition of the "search on answer" pattern and the ability to design a feasibility check using greedy reasoning. The greedy sorting method shows deeper insight into energy distribution and can lead to an elegant constant‑space implementation, but the binary search version is usually easier to reason about under interview pressure.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy with Sorting | O(m log m) | O(1) | When you want a direct mathematical distribution approach and are comfortable reasoning about removing oversized batteries. |
| Binary Search on Maximum Time | O(m log S) | O(1) | General case and most common interview solution using feasibility check with binary search. |