<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:
        # binary search on solution space
        # note that if we can run computes for 2 mins, we can run them for 1 min, 0 min, etc
        # max is total battery life divided by computers
        left = 0
        right = sum(batteries) // n
        # solution - required intuition to solve optimially
        # is to realize that if a battery has run time greater than
        # the target time, then there is no way we can use
        # excess amount of battery to power any other computer
        # eg. n = 3, b = [1,3,5]
        # 1, [0,2,4], only possible solution, so cannot just add battery time and divide
        # but if we take min of (b,1), then we get 3/3 = 1, so that is the only answer

        # return true if n computes can run simulatenous for atleast  k time
        # can be done in linear time
        def checkOpt(batteries, n, k):
            # check if we run a computer for at least k time
            time = 0
            for b in batteries:
                # if battery is smaller than k time, use all the power
                # if battery is greater than k time, then just use that k power
                time += min(b, k)

            # return true if we can power n computers
            return (time//n) >= k
        
        # return true if n computes can run simulatenous for atleast  k time
        def checkBrute(batteries, n, k):
            # keep heap of max battery life?
            # for n times, pop from batteries
            # and decrement by 1 and put back onto the heap
            maxHeap = [-b for b in batteries] # O(batteries)
            heapify(maxHeap) # linear time from builtin function
            time = 0 # number of mins n computes simul. ran for

            while len(maxHeap) >= n:
                # take n most useful batteries, and simulate using them for 1 minute
                nextBatteries = [] # store batteries to be placed into next batch
                for _ in range(n):
                    newBattery = heappop(maxHeap)+1  # add since it is a negative number
                    if newBattery < 0: # if still charge in battery
                        nextBatteries.append(newBattery)

                for b in nextBatteries:
                    heappush(maxHeap, b)

                time += 1
            return time >= k

        while left <= right:
            mid = (left+right)//2
            if checkOpt(batteries, n, mid): # want vals from 0 to answer to return true
                left = mid + 1
            else:
                right = mid -1
        return right
1727