<p>You have <code>n</code> computers. You are given the integer <code>n</code> and a <strong>0-indexed</strong> integer array <code>batteries</code> where the <code>i<sup>th</sup></code> battery can <strong>run</strong> a computer for <code>batteries[i]</code> minutes. You are interested in running <strong>all</strong> <code>n</code> computers <strong>simultaneously</strong> using the given batteries.</p>

<p>Initially, you can insert <strong>at most one battery</strong> into each computer. After that and at any integer time moment, you can remove a battery from a computer and insert another battery <strong>any number of times</strong>. The inserted battery can be a totally new battery or a battery from another computer. You may assume that the removing and inserting processes take no time.</p>

<p>Note that the batteries cannot be recharged.</p>

<p>Return <em>the <strong>maximum</strong> number of minutes you can run all the </em><code>n</code><em> computers simultaneously.</em></p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2022/01/06/example1-fit.png" style="width: 762px; height: 150px;" />
<pre>
<strong>Input:</strong> n = 2, batteries = [3,3,3]
<strong>Output:</strong> 4
<strong>Explanation:</strong> 
Initially, insert battery 0 into the first computer and battery 1 into the second computer.
After two minutes, remove battery 1 from the second computer and insert battery 2 instead. Note that battery 1 can still run for one minute.
At the end of the third minute, battery 0 is drained, and you need to remove it from the first computer and insert battery 1 instead.
By the end of the fourth minute, battery 1 is also drained, and the first computer is no longer running.
We can run the two computers simultaneously for at most 4 minutes, so we return 4.

</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2022/01/06/example2.png" style="width: 629px; height: 150px;" />
<pre>
<strong>Input:</strong> n = 2, batteries = [1,1,1,1]
<strong>Output:</strong> 2
<strong>Explanation:</strong> 
Initially, insert battery 0 into the first computer and battery 2 into the second computer. 
After one minute, battery 0 and battery 2 are drained so you need to remove them and insert battery 1 into the first computer and battery 3 into the second computer. 
After another minute, battery 1 and battery 3 are also drained so the first and second computers are no longer running.
We can run the two computers simultaneously for at most 2 minutes, so we return 2.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= batteries.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= batteries[i] &lt;= 10<sup>9</sup></code></li>
</ul>

class Solution:
    def maxRunTime(self, n: int, batteries: List[int]) -> int:
        """
        If we can implement an oracle f, such that f(x) returns whether a running time
        of x is possible, then we are done.

        This is because if a running time of x is possible, then all running times
        less than or equal to x are possible, because we can always just remove all
        of the batteries at any timestep y <= x.

        So if a running time of x is not possible, then we know the true answer is
        strictly less than x. And if a running time of x is possible, then we know
        the true answer is at least x.

        Now the question is how to implement the oracle f.

        First note that if batteries[i] >= x, then we know that battery must be used
        to power exactly one computer. So remove computers until we know the array
        only has batteries whose power is < x. This is OK because if a battery
        with batteries[i] >= x is used to try and power multiple computers, then
        because it cannot do so simultaneously, such a solution is suboptimal.
        This argument is a bit shaky, but it is intuitive enough.

        Now we have an array where all the batteries have power < x. So form a
        grid where the x axis has m computers left and the y axis has x increments.
        We want to place batteries on each entry of the grid, such that each row
        has unique values (i.e., the same battery is not used for multiple computers
        at the same timestep). To do so, we simply start at the first column and
        start placing batteries. Since each battery's power is less than x, each
        column has at least two batteries. If we place a battery at the end of a
        column and it has power left over, then we just place it again at the
        beginning (first row) of the next column. Since battery powers are all
        less than x, and the height of each column is x, we are guaranteed that
        each row has unique values since batteries never overlap. If we can cover
        the whole grid, then f(x) is true, otherwise it is false.
        """
        m = len(batteries)
        batteries.sort()

        left, right = min(batteries), math.floor(sum(batteries) / n)
        while left < right - 1:
            mid = (left + right) // 2
            if self.f(mid, batteries, n):
                left = mid
            else:
                right = mid - 1
        if self.f(right, batteries, n):
            return right
        return left


    def f(self, x, batteries, n):
        total = x * n
        for power in batteries:
            if power >= x:
                total -= x
            else:
                total -= power
        return total <= 0
931