Python3 - Binary Search - Beats 99% - intuition, math, code explained
IntuitionWe have multiple mechanics  that finish cars in varying amounts of time. They are ranked, so we know that at worst, the best mechanic can handle all ca
# Intuition
We have multiple mechanics  that finish cars in varying amounts of time. They are ranked, so we know that at worst, the best mechanic can handle all cars in the shop in a certain amount of time - we will call $$b$$. We  know that 1 minute would be the fastest possible amount of time. We also know that multiple mechanics can work in parallel, meaning a faster time is possible than just having the best mechanic do everything.

We are looking for the minimum number of minutes in a range, and as described above, we have a range $$1$$ - $$b$$

Therefore, binary search is an ideal solution for efficiently finding the minimum number of minutes. We simply do a binary search with 1 as the low and $$b$$ as the high. 

We also have a formula for determining how long it takes for a mechanic to fix n number of cars. The formula is a quadratic equation... $$r * c^2 = m$$ where $$r$$ is the rank of the mechanic, $$c$$ is the number of cars they can finish and $$m$$ is the number of minutes it takes them.


<!-- Describe your first thoughts on how to solve this problem. -->

# Approach
<!-- Describe your approach to solving the problem. -->
If we use a binary search to plug in possible values of $$m$$, and we know the ranking ($$r$$) of each mechanic, we can easily turn the quadratic equation into a quadratic inequality to test whether any given number of minutes $$m$$ is possible. If it is, we can keep lowering $$m$$ until it isn't possible, and then we have our answer.

For each possible value of $$m$$ we would need to determine if $$m$$ minutes is enough time for $$c$$ cars to be fixed by the available mechanices with $$r$$ rankings.

To determine that formula, we would need to change the formula to solve for $$c$$ instead of solving for $$m$$.

$$r * c^2 \leq m$$
$$c^
2
 ≤ 
m/r
​$$
$$c\leq sqrt(m/r)$$

So - for each $$m$$, `total_cars += sqrt(m/r)` for each mechanic. If `total_cars >= cars` the $$m$$ is a viable number and we can keep searching lower.

## The Code
1. Initialize `left` and `right` to 1 and `min(ranks) * cars^2`. This high represents the best mechanic handling all cars himself.
2. Perform a standard binary search loop - each iteration, determine the total number of cars that can be handled by each mechanic in that amount of time.
3. If that total is >= `cars`, set `high` equal to `mid`. If not, set `mid` to `left` + 1.
4. Return `left` as the minimum number of minutes all cars can be fixed.

# Code
```python3 []
class Solution:
    def repairCars(self, ranks: List[int], cars: int) -> int:
        left, right = 1, min(ranks) * cars**2
        while left < right:
            mid = (right + left) // 2
            total_cars = 0
            for rank in ranks:
                total_cars += isqrt(mid//rank)
                if total_cars >= cars:
                    break
            if total_cars >= cars:
                right = mid
            else:
                left = mid + 1
            
        return left
```
['Array', 'Binary Search', 'Python3']