Maximum Running Time of N Computers — Hard Problem & Solution

You want to run n computers simultaneously. Battery i can power one computer for batteries[i] minutes.

Difficulty: Hard
Topics: Arrays, Greedy, Sorting, Binary Search
Asked at: Amazon, Google, Intuit
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You want to run n computers simultaneously. Battery i can power one computer for batteries[i] minutes.

At any integer minute you may swap batteries between computers, as often as you like, but a battery powers at most one computer at a time. Return the maximum number of minutes all n computers can run together.

Example 1

Input: n = 2, batteries = [3,3,3]
Output: 4
Explanation: Run two batteries for 2 minutes, then rotate the third in.

Example 2

Input: n = 2, batteries = [1,1,1,1]
Output: 2

Example 3

Input: n = 3, batteries = [10,10,3,5]
Output: 8
Explanation: Three computers for 8 minutes need 24 battery-minutes, and capping each battery at 8 supplies exactly 8+8+3+5.

Constraints

1 <= n <= batteries.length <= 1000
1 <= batteries[i] <= 1000000

How to solve Maximum Running Time of N Computers

Binary search the running time. For a target t, each battery's usable contribution is capped at t — no single computer can use more than t minutes from one battery — and any allocation meeting the total demand t · n can actually be scheduled.

Approach

Search t over [0, total / n].
can(t): check sum(min(batteries[i], t)) >= t · n.
Take the largest feasible t with the upper-biased midpoint.

Why it works

The cap is necessary because a battery powers one computer at a time, so it can supply at most t of the t minutes. It is also sufficient: with every battery capped at t, the capped amounts can be laid out across the n computers' timelines greedily without any battery overlapping itself — exactly the classic scheduling argument for splittable jobs with a per-job cap. Raising t raises the demand faster than the capped supply, so feasibility is monotone.

Complexity

Time — O(m log(total / n))
Space — O(1)

Pitfalls

t · n reaches about 10^9 · 10^3 = 10^12 — the comparison needs 64-bit.
Without the min(·, t) cap, one huge battery would appear to power everything.
The upper-biased midpoint is needed for a maximise search.

Reference solution

Python

from typing import List

def maxRunTime(n: int, batteries: List[int]) -> int:
    lo, hi = 0, sum(batteries) // n

    def can(t: int) -> bool:
        if t == 0:
            return True
        need = t * n
        total = 0
        for b in batteries:
            total += min(b, t)
            if total >= need:
                return True
        return total >= need

    while lo < hi:
        mid = (lo + hi + 1) // 2
        if can(mid):
            lo = mid
        else:
            hi = mid - 1
    return lo

JavaScript

var maxRunTime = function(n, batteries) {
    var total = 0, i;
    for (i = 0; i < batteries.length; i++) total += batteries[i];
    var can = function(t) {
        if (t === 0) return true;
        var sum = 0, need = t * n;
        for (var j = 0; j < batteries.length; j++) {
            sum += Math.min(batteries[j], t);
            if (sum >= need) return true;
        }
        return sum >= need;
    };
    var lo = 0, hi = Math.floor(total / n);
    while (lo < hi) {
        var mid = Math.ceil((lo + hi) / 2);
        if (can(mid)) lo = mid; else hi = mid - 1;
    }
    return lo;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue