Maximum Running Time of N Computers

main.md

Question

Approach

I binary-search the maximum running time T. For a candidate T I check if the total available minutes (summing min(b, T) for every battery b) is at least n * T — because each computer needs T minutes and a single battery can contribute at most T minutes toward a given computer. If the check passes, T is feasible and I try larger values; otherwise I try smaller ones.

Implementation

class Solution:
    def maxRunTime(self, n: int, batteries: List[int]) -> int:
        total = sum(batteries)

        lo, hi = 0, total // n

        def feasible(T: int) -> bool:
            need = n * T
            s = 0
            for b in batteries:
                s += b if b <= T else T
                if s >= need:
                    return True
            return False

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

        return lo

Complexities

• Time: O(m * log S)
• Space: O(1)

The algorithm is "ONLY" optimal in theory, but performance could degrade/become slow with very large inputs because it keeps checking all the batteries over and over in each step. 😉

Oh. That's because that was the solution I could come up with. Not meant to be perfect but can be iterated upon

Btw, there are better ways. Have a good night