<p>You are given an integer array <code>ranks</code> representing the <strong>ranks</strong> of some mechanics. <font face="monospace">ranks<sub>i</sub></font> is the rank of the <font face="monospace">i<sup>th</sup></font> mechanic<font face="monospace">.</font> A mechanic with a rank <code>r</code> can repair <font face="monospace">n</font> cars in <code>r * n<sup>2</sup></code> minutes.</p>

<p>You are also given an integer <code>cars</code> representing the total number of cars waiting in the garage to be repaired.</p>

<p>Return <em>the <strong>minimum</strong> time taken to repair all the cars.</em></p>

<p><strong>Note:</strong> All the mechanics can repair the cars simultaneously.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> ranks = [4,2,3,1], cars = 10
<strong>Output:</strong> 16
<strong>Explanation:</strong> 
- The first mechanic will repair two cars. The time required is 4 * 2 * 2 = 16 minutes.
- The second mechanic will repair two cars. The time required is 2 * 2 * 2 = 8 minutes.
- The third mechanic will repair two cars. The time required is 3 * 2 * 2 = 12 minutes.
- The fourth mechanic will repair four cars. The time required is 1 * 4 * 4 = 16 minutes.
It can be proved that the cars cannot be repaired in less than 16 minutes.​​​​​
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> ranks = [5,1,8], cars = 6
<strong>Output:</strong> 16
<strong>Explanation:</strong> 
- The first mechanic will repair one car. The time required is 5 * 1 * 1 = 5 minutes.
- The second mechanic will repair four cars. The time required is 1 * 4 * 4 = 16 minutes.
- The third mechanic will repair one car. The time required is 8 * 1 * 1 = 8 minutes.
It can be proved that the cars cannot be repaired in less than 16 minutes.​​​​​
</pre>

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

<ul>
	<li><code>1 &lt;= ranks.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= ranks[i] &lt;= 100</code></li>
	<li><code>1 &lt;= cars &lt;= 10<sup>6</sup></code></li>
</ul>

class Solution:
    def repairCars(self, ranks: List[int], cars: int) -> int:

        def Sqrt(X: float) -> float:
            return X ** 0.5
        
    # this version is for minimizing something.

        def canDoAllCarsInTargetMinutes(target: int) -> bool:
            # print(f'Testing time={target}')
            if target == 0 and cars != 0:
                # cannot finish if we have no time
                return False
            carsDone = 0
            # minutes = R * N^2
            # -> N^2 = minutes / R
            # -> N = Sqrt(minutes / R)
            for R in ranks:
                carsDoneByThisMechanic = int(Sqrt(target / R))
                # print(f'  {R=} cars={carsDoneByThisMechanic}')
                # timeTaken = R * carsDoneByThisMechanic * carsDoneByThisMechanic
                # print(f'    time={timeTaken}')
                # assert timeTaken <= target
                carsDone += carsDoneByThisMechanic
            # print(f'-->Total {carsDone=}')
            return (carsDone >= cars)

        L = 0
        left = canDoAllCarsInTargetMinutes(L)
        if left:
            print(f'Strange, {L=} is true')
            return L
        # worst case: all cars (N^2) done by worst mechanic (r = max(ranks))
        R = max(ranks) * cars * cars
        right = canDoAllCarsInTargetMinutes(R)
        if not right:
            print(f'Strange, {R=} is false')
            return -1
        print(f'[{L},{R}] ({left},{right})')
        while L + 1 < R:
            M = (L + R) // 2
            mid = canDoAllCarsInTargetMinutes(M)
            print(f'[{L},{M},{R}] ({left},{mid},{right})')
            if mid:
                print(f'  True: replace Right')
                (R, right) = (M, mid)
            else:
                print(f'  False: replace Left')
                (L, left) = (M, mid)

        print(f'[{L},{R}] ({left},{right})')
        # R is now the lowest possible True value
        return R

1638