Python | 8ms | Improved Heap | Beats 98-99%
ApproachLet R=[r1​,r2​,r3​,...,rk​] be our list of ranks and let C be the number of cars. Our goal is to find a distribution D=[c1​,c2​,c3​,...,ck​] such that a
# Approach
<!-- Describe your approach to solving the problem. -->
Let $R=\left[r_1,r_2,r_3,...,r_k\right]$ be our list of ranks and let $C$ be the number of cars. Our goal is to find a distribution $D = \left[c_1,c_2,c_3,...,c_k\right]$ such that all $c_n$ are nonnegative, $c_1+c_2+c_3+\dots+c_k=C$, and $\max(r_nc_n^2)$ over all $n$ is minimized, where $1\le n \le k$. Ideally, this happens when all $r_nc_n^2$ are the same value. So, we can find this "ideal distribution" by setting $r_ic_i^2=r_jc_j^2$ for all valid $i,j$, which we can rearrange to yield $c_i=c_j\sqrt{\frac{r_j}{r_i}}$. Using our equation $c_1+c_2+c_3+\dots+c_k=C$, we can derive that $c_i=\frac{C}{S\sqrt{r_i}}$, where $S=\frac{1}{\sqrt{r_1}}+\frac{1}{\sqrt{r_2}}+\frac{1}{\sqrt{r_3}}+\dots+\frac{1}{\sqrt{r_k}}$.
$\newline$
Unfortunately, we cant directly use this ideal distribution to find our answer because there is no guarantee that each $c_i$ will be an integer. However, we can use this ideal distribution as a baseline which we can build upon to produce our final solution where all $c_i$ are integers. So, we initialize our distribution as $D=\left[\left\lfloor c_1 \right\rfloor, \lfloor c_2 \rfloor, \lfloor c_3 \rfloor,\dots,\lfloor c_k \rfloor\right]$ and calculate how many cars we have left to place in the distribution. Then, we implement a heap-based algorithm to place those remaining cars in the distribution (I won't bother covering how this algorithm works because a lot of other solutions already talk about it). Overall, this algorithm runs much faster than a plain heap-based solution as we start with a distribution that is on average very close to the actual solution, so we are able to perform less calculations overall.

# Code
```python3 []
class Solution:
    def repairCars(self, ranks: List[int], cars: int) -> int:
        actual_ranks = Counter(ranks)
        heap = []
        S = cars / sum(count / math.sqrt(rank) for rank,count in actual_ranks.items())
        time = 0

        for rank,count in actual_ranks.items():
            val = int(S // math.sqrt(rank))
            cars -= val * count
            time = max(time, rank * val * val)
            val += 1
            heap.append([rank * val * val, rank, val, count])
        
        heapify(heap)

        while cars > 0:
            time, rank, val, count = heappop(heap)
            cars -= count
            val += 1
            heappush(heap, [rank * val * val, rank, val, count])
        
        return time

```
['Math', 'Heap (Priority Queue)', 'Python3']