Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

For a proposed runtime t, a battery can contribute at most min(capacity, t) minutes because it cannot power two computers simultaneously. These contributions suffice when their total reaches n*t: trim excess and fill n timelines of length t consecutively. A battery split across a boundary occupies one timeline's tail and the next timeline's head; these do not overlap in time because its total contribution is at most t. All boundaries are integer minutes. Feasibility is monotone in t.

Approach

Binary-search between one minute and the total capacity divided by n, rounded down; the constraints provide enough positive-capacity batteries for the lower bound. For each candidate, sum capped contributions and test whether they supply all computers for that duration. Use an upper midpoint, raising the feasible lower bound or lowering the infeasible upper bound. Return the largest feasible runtime. Capping each battery is essential: total capacity alone can overestimate what an oversized battery can deliver concurrently.

class Solution:
    def maxRunTime(self, n: int, batteries: List[int]) -> int:
        l, h = 1, sum(batteries) // n

        while l < h:
            target = l + (h - l + 1) // 2
            available = 0
            for x in batteries:
                available += min(target, x)

            if available // n >= target:
                l = target
            else:
                h = target - 1

        return l

Complexity analysis

Let b = batteries.length and S = floor(sum(batteries) / n). Both implementations take O(b log(S + 1)) time, including the initial sum and each linear feasibility scan. Auxiliary space is O(1). The +1 retains the initial O(b) work when S = 1.