<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>

# You are given an integer array ranks

# -len(ranks) large
# -ranks[i] small
# -cars large

# ranksi is the rank of the ith mechanic
# A mechanic with a rank r can repair n cars in r * n2 minutes.
# You are also given an integer cars representing the total number of cars waiting in the garage to be repaired.
# Return the minimum time taken to repair all the cars.
# - return minimum amount considering each mechanic takes r*n2 to fix each car
#     - higher ranks will take more time
#     - lower ranks will take less time
#         - take to fix will balance out to be at most some max value
#     - a mechanic taking a car will reduce cars needed to be fixed
#         - a mechanic can take all the cars (but will result in a very high value)
# no idea what is a good approach here
#     - keep track of LARGEST value for ALL mechanics
#         - keep track of globally how many cars are left
#             - keep track of cars assigned in another array corresaponding to i
#             - SEARCH for a mechanic that we can give a car to resulting in the smallest increase of total value
#                 - in each search iteration, search for smallest increase to the currVal
#                     - value of mechanic time = ranks[i] * carsAssigned[i]*carsAssigned[i]

# example:
#     -Input: ranks = [4,2,3,1], cars = 10

#     cars 10 currVal 0, ranks 4 2 3 1 carsAssigned 0 0 0 0:
#         - which mechanic can give smallest increase?:
#             - rank 1 mechanic, 1 * 1 * 1 = 1 (chosen)
#             - rank 2 mechanic, 2 * 1 * 1 = 2
#             - ......
#     cars 9 currVal 1, ranks 4 2 3 1, 
#         - which mechanic can give smallest increase?:
#             - rank 1 mehcanic, 1 * 2 * 2 = 4
#             - rank 2 mechanic, 2 * 1 * 1 = 2 (chosen)
#             - rank 3 mechanic, 3 * 1 * 1 = 3
#             - rank 4 mechanic, 4 * 1 * 1 = 4

# binary search, using middle array value to search for the smallest increase of currVal
#     - ASSUMING THERE IS SOME TYPE OF SORTEDNESS
#     - CHEATED BY LOOKING AT TOPICS
# no binary search, will do a linear search for the best option.
# too slow
# use BINARY search on CARS to find lowest val for each mechanic?
# RANKS LEN IS HUGE, sort ranks first then BINARY SEARCH
# Binary search what?
#     - pivot?
#         - middle of 0 and cars
#         - what are we searching for?
#         - find largest number? we already know what that is when sorted
#             - lower numbers amount of cars that can repair = larger * x * x 
# HINT 1: for a predetermined time can cars be fixed?
# HINT 2: for try using binary search on the answer

# approach 1: find largest rank and get largest value
#     example:
#     -Input: ranks = [4,2,3,1], cars = 10

#     largest = 4
#     value for 10 cars on rank 4, 4 * 10 * 10 = 400
#     value for 0 cars on rank 4, 4 * 0 * 0 = 0
#     - now binary search on answer value, 400
#         pivot = 200
#         does 200 work?
#             - get mechanic i and add cars until value = 200 or cars < 0
#             - if cars is greater than 0, need more value so go upper half
#             - else go to lower half


        
class Solution:
    def repairCars(self, ranks: List[int], cars: int) -> int:
        largest = 0
        for i in range(len(ranks)):
            if ranks[i] > ranks[largest]:
                largest = i
        lo = 0
        hi = ranks[largest] * cars * cars
        while lo <= hi:
            pivot = (lo + hi) // 2
            countCars = 0
            for i in ranks:
                countCars += math.floor(math.sqrt(pivot//i))
            if countCars < cars:
                lo = pivot + 1
                pivot = lo
            else:
                hi = pivot - 1
        return pivot


            
        
1197