Maximum Running Time of N Computers
Problem
You have n identical computers and a pile of batteries, where batteries[i] can power one computer for that many minutes. At any moment you may swap batteries between computers — swapping is instant and unlimited — but charge is never regained: a battery's remaining minutes only go down while it powers a machine, and one battery can drive only one computer at a time.
Return the maximum number of whole minutes you can keep all n computers running simultaneously. Constraints: 1 ≤ n ≤ batteries.length ≤ 10⁵, 1 ≤ batteries[i] ≤ 10⁹.
n = 2, batteries = [3, 3, 3]4def max_run_time(n, batteries):
total = sum(batteries)
lo, hi = 1, total // n
ans = 0
while lo <= hi:
mid = (lo + hi) // 2
usable = sum(min(b, mid) for b in batteries)
if usable >= n * mid:
ans = mid
lo = mid + 1
else:
hi = mid - 1
return ansfunction maxRunTime(n, batteries) {
const total = batteries.reduce((a, b) => a + b, 0);
let lo = 1, hi = Math.floor(total / n), ans = 0;
while (lo <= hi) {
const mid = Math.floor((lo + hi) / 2);
let usable = 0;
for (const b of batteries) usable += Math.min(b, mid);
if (usable >= n * mid) {
ans = mid;
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return ans;
}long maxRunTime(int n, int[] batteries) {
long total = 0;
for (int b : batteries) total += b;
long lo = 1, hi = total / n, ans = 0;
while (lo <= hi) {
long mid = (lo + hi) / 2;
long usable = 0;
for (int b : batteries) usable += Math.min(b, mid);
if (usable >= n * mid) {
ans = mid;
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return ans;
}long long maxRunTime(int n, vector<int>& batteries) {
long long total = 0;
for (int b : batteries) total += b;
long long lo = 1, hi = total / n, ans = 0;
while (lo <= hi) {
long long mid = (lo + hi) / 2;
long long usable = 0;
for (int b : batteries) usable += min((long long)b, mid);
if (usable >= (long long)n * mid) {
ans = mid;
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return ans;
}Explanation
Instead of asking "how long can the computers run?" we ask the much easier yes/no question: can all n computers run for t minutes? A battery powers only one computer at a time, so even a giant battery contributes at most t useful minutes during a window of length t. The total usable energy is therefore Σ min(bᵢ, t), and keeping n machines alive for t minutes consumes exactly n·t. The key claim: t is feasible if and only if Σ min(bᵢ, t) ≥ n·t.
Necessity is the counting argument above. For sufficiency, think greedily: dedicate every battery with bᵢ ≥ t to its own computer. Each remaining battery holds less than t minutes, so by round-robin swapping the leftover machines can sip from the pooled small batteries without ever needing one battery in two places at once — the pool drains like a shared tank, and the inequality says the tank is big enough.
Feasibility is monotone: if t minutes works, every shorter time works too, so the answer is the largest feasible t and binary search applies. The answer can never exceed ⌊total / n⌋ (perfectly shared energy), which gives the upper bound of the search window.
Default example: n = 2, batteries = [3, 3, 3], total 9, so search t in [1, 4]. t = 2: usable 6 ≥ 4, feasible — go higher. t = 3: usable 9 ≥ 6, feasible — go higher. t = 4: usable min(3,4)·3 = 9 ≥ 8, feasible — go higher, but the window is empty. The answer is 4: run both machines 3 minutes on two batteries, then split the third battery's 3 minutes across the last minute of each plus a swap.
Each feasibility check scans the m batteries once, O(m), and the binary search halves a window of size total / n, so the total cost is O(m · log(total / n)) with O(1) extra space.