Maximum Running Time of N Computers

Links to Other Solutions

Problem Description

So, you’ve got N computers, and they all need power. Sounds simple, right? But wait! You’ve got a limited number of batteries, and they’re not exactly the Energizer Bunny. They don’t keep going and going; they just… stop. The challenge here is to figure out how long you can keep these computers running before they all throw a tantrum and shut down.

Imagine you’re at a party, and you’ve got a limited supply of snacks. You want to make sure everyone gets a bite, but some friends are hogging the chips while others are just nibbling on a carrot stick. You need to balance the snacks (or batteries, in this case) to keep the party (or computers) going as long as possible.

Code Solution


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

        batteries.sort()

        while batteries[-1] > summ // n:
            summ -= batteries.pop()
            n -= 1

        return summ // n

Approach Explanation

The approach taken in this solution is quite clever. First, we calculate the total power available from all batteries. Then, we sort the batteries to easily access the largest one. If the largest battery has more power than the average power per computer, we can afford to remove it and redistribute its power among the remaining batteries. This process continues until we reach a point where the largest battery is no longer greater than the average. Finally, we return the average running time, which is the total power divided by the number of computers.

Time and Space Complexity

Time Complexity: O(n log n) due to the sorting of the batteries.
Space Complexity: O(1) since we are using a constant amount of space, aside from the input.

Real-World Example

Let’s say you’re organizing a movie night with friends, and you have a limited number of snacks (batteries). If one friend decides to take all the popcorn (the largest battery), the others will be left with just a few chips (smaller batteries). To keep everyone happy (or in this case, keep the computers running), you need to redistribute the snacks. The goal is to make sure everyone has enough to enjoy the movie without running out of snacks too soon.