Find the Earliest Time All Parallel Mechanics Finish
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
Mechanic `i` has rank `ranks[i]` and needs `ranks[i] * c * c` minutes to repair `c` cars. All mechanics work simultaneously. Given the total number `cars`, return the minimum time in minutes needed to finish repairing them all.
```cpp
class Solution {
public:
long long repairCars(vector<int>& ranks, int cars);
};
```
### Examples
**Example 1:**
```text
Input: ranks = [2,3], cars = 3
Output: 8
Explanation: By minute 8 the rank-2 mechanic repairs two cars and the rank-3 mechanic repairs one. Before minute 8, each can repair at most one.
```
**Example 2:**
```text
Input: ranks = [4], cars = 2
Output: 16
Explanation: The sole mechanic needs 4*2*2 minutes.
```
### Constraints
- `1 <= ranks.length <= 100000`.
- `1 <= ranks[i] <= 100`.
- `1 <= cars <= 1000000`.
### Clarifying Questions
- Do mechanics work one after another? No; they work in parallel.
- Is the time for c cars linear in c? No; it is rank times c squared.
- Must each mechanic repair a car? No.
- Is the returned time approximate? No; return the minimum integer time.
```hint Check the boundary
Check a proposed allocation by taking the largest mechanic completion time, rather than summing completion times.
```
Overview: Find the minimum time for parallel mechanics to repair all cars when a rank-r mechanic needs r times the square of its assigned car count.