< Back





2141. Maximum Running Time of N Computers

We're given a list of batteries where batteries[i] describes the minutes of power a particular
battery has. We're asked to determine how many minutes we can power n computers simultaneously.
Being a binary search problem, our search space is minutes, and we're trying to determine at each
step of the binary search if the minutes we've chosen are too much or too little for the batteries
we're given.

At each step of the binary search, we sum the power of the batteries, summing the minimum of power
vs the target amount of minutes for this step. If the energy we can pull together to simultaneously
run n machines provides us with greater than or equal to minutes vs m, we move the left pointer to
the right - we need to decrease our search space because it looks like we can still power the n
computers simultaneously.

In contrast, if we're not able to make the power requirements in the time we're aiming for, we need
to decrease our search space by moving the right pointer to the left - looks like our goals are too
ambitious for the amount of power we have available.

Eventually the binary search will terminate, and the left pointer will represent the maximum time
we can power n computers simultaneously with the batteries provided.

The solution is as follows:


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

          while l < r:
              m = r - (r - l) // 2
              energy = sum(min(power, m) for power in batteries)

              if energy // n >= m:
                  l = m
              else:
                  r = m - 1

          return l


_ Time Complexity:

  O(m log(k)) - m is the length of the battiers array, and k is the maximum power of one battery.

_ Space Complexity:

  O(1) - Binary search requires constant space.