# Minimum Time to Repair Cars
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-time-to-repair-cars)
Canonical: https://scaleengineer.com/dsa/problems/minimum-time-to-repair-cars
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array
**Companies:** [Deloitte](https://scaleengineer.com/companies/deloitte), [HashedIn](https://scaleengineer.com/companies/hashedin)
---
## Problem
You are given an integer array `ranks` representing the **ranks** of some mechanics. 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._

**Note:** All the mechanics can repair the cars simultaneously.

**Example 1:**

**Input:** ranks = [4,2,3,1], cars = 10
**Output:** 16
**Explanation:** 
- 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.​​​​​

**Example 2:**

**Input:** ranks = [5,1,8], cars = 6
**Output:** 16
**Explanation:** 
- 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.​​​​​

**Constraints:**

* `1 <= ranks.length <= 105`
* `1 <= ranks[i] <= 100`
* `1 <= cars <= 106`

# Approaches
## Priority Queue (Min-Heap) Approach
This approach uses a greedy strategy with a min-heap (Priority Queue) to simulate the assignment of cars. The core idea is to iteratively assign each car to the mechanic who can complete their *next* repair job in the minimum amount of time. By doing this for all `cars`, the maximum time encountered during this process will be the minimum time required for all repairs.
**Time:** O(C * log(K)), where `C` is the number of `cars` and `K` is the number of mechanics. Initializing the heap takes O(K), but this is dominated by the main loop which runs `C` times, with each heap operation (poll and offer) taking `O(log K)` time. · **Space:** O(K), where `K` is the number of mechanics (`ranks.length`). The priority queue stores one entry for each mechanic.
**Pros:** The greedy logic is relatively straightforward to understand.; It correctly finds the minimum time by always choosing the locally optimal next assignment.
**Cons:** The time complexity is dependent on the number of `cars`, which can be large (`10^6`). This makes it less efficient than the binary search approach for the given constraints.; For very large values of `cars`, this approach might result in a 'Time Limit Exceeded' error on some platforms.
### Explanation
We can model this problem as a simulation where we have `cars` repair tasks to distribute among the available mechanics. A greedy approach is to always assign the next task to the mechanic who can finish it the fastest, thus minimizing the time at each step.

A min-priority queue is the perfect data structure for this. It can keep track of the mechanics and always provide us with the one who is 'next available' at the earliest time.

The state stored in the priority queue for each mechanic will be `(time, n, r)`, where `r` is the mechanic's rank, `n` is the number of cars they are currently assigned, and `time` is the total time they would take (`r * n^2`). The priority queue is ordered by `time`.

Initially, we populate the queue with the time it would take for each mechanic to repair just one car. Then, we loop `cars` times. In each loop, we 'assign' one car by:
1. Polling the mechanic with the minimum completion time from the queue.
2. This time becomes our current maximum time (the bottleneck).
3. We then update this mechanic's state, calculating the new time it would take if they were to repair one more car, and push this updated state back into the queue.

After `cars` such assignments, the final `maxTime` recorded is the answer.

```java
import java.util.PriorityQueue;

class Solution {
    public long repairCars(int[] ranks, int cars) {
        // Each element in the PQ is an array: {time, num_cars_repaired, rank}
        // We use long for time to avoid overflow.
        PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));

        for (int rank : ranks) {
            // Initially, each mechanic is considered for repairing 1 car.
            // Time = rank * 1 * 1
            pq.offer(new long[]{rank, 1, rank});
        }

        long maxTime = 0;
        // We perform `cars` assignments.
        for (int i = 0; i < cars; i++) {
            long[] current = pq.poll();
            long time = current[0];
            long n = current[1];
            long rank = current[2];

            maxTime = time;

            // This mechanic is now assigned `n` cars. We calculate the time
            // for them to repair `n+1` cars and add it back to the queue.
            long nextN = n + 1;
            long nextTime = rank * nextN * nextN;
            pq.offer(new long[]{nextTime, nextN, rank});
        }

        return maxTime;
    }
}
```
### Algorithm
- Create a min-priority queue to store tuples representing the state of each mechanic. Each tuple will be of the form `(time_to_finish, cars_repaired, rank)`.
- Initially, populate the priority queue for each mechanic. If a mechanic with rank `r` repairs one car, it takes `r * 1^2 = r` time. So, for each `rank` in `ranks`, push `(rank, 1, rank)` into the queue.
- We need to assign a total of `cars` repair jobs. We can simulate this by iterating `cars` times.
- In each of the `cars` iterations:
  - Extract the mechanic who can finish their *next* assigned car the earliest. This is the element with the minimum `time_to_finish` from the priority queue. Let this be `(time, n, r)`.
  - This `time` becomes our current potential answer for the minimum time required, as it's the bottleneck so far.
  - Now that this mechanic has completed `n` cars, we calculate the time it would take for them to complete `n + 1` cars: `new_time = r * (n+1)^2`.
  - We push the new state `(new_time, n + 1, r)` back into the priority queue.
- After `cars` iterations, the last `time` extracted from the queue is the minimum time required to repair all `cars`, because at each step we satisfied one car repair requirement in the most optimal way, and the total time is determined by the last (i.e., the longest) repair assignment.

## Binary Search on the Answer
The most efficient approach leverages the monotonic nature of the problem. The feasibility of repairing all cars within a certain time `t` is a monotonic function: if it's possible for time `t`, it's also possible for any time greater than `t`. This property makes the problem a perfect candidate for binary search on the answer.

We can search for the minimum time `t` in a defined range. For any given time `t`, we can easily calculate the total number of cars that can be repaired by all mechanics combined. This check allows us to efficiently determine whether to search for a smaller or larger time in our binary search.
**Time:** O(K * log(M)), where `K` is the number of mechanics (`ranks.length`) and `M` is the size of the search space for time (from 0 to `max_rank * cars^2`). Since `log(M)` is a large but effectively constant number (e.g., `log(10^14)` is about 47), the complexity is dominated by the `K` term. · **Space:** O(1), as the algorithm only requires a few variables to store the search boundaries and the answer. No additional data structures that scale with input size are needed.
**Pros:** Extremely efficient, with a time complexity that is nearly linear in the number of mechanics and logarithmic in the (very large) time range.; The space complexity is constant, making it very memory-efficient.; It is the optimal solution for the given problem constraints.
**Cons:** The concept of binary searching on the answer can be less intuitive than a direct simulation.; Requires careful handling of the search space boundaries and potential integer overflows, necessitating the use of `long` for time calculations.
### Explanation
The key insight is to reframe the problem from "what is the minimum time?" to "is it possible to repair all cars within time `t`?". This is a decision problem that is much easier to solve.

For a given time `t`, a mechanic with rank `r` can repair `n` cars if `r * n^2 <= t`. This implies `n <= sqrt(t / r)`. The maximum number of cars this mechanic can repair is `floor(sqrt(t / r))`. By summing this value over all mechanics, we get the total number of cars that can be repaired within time `t`.

Let's call this check `canRepair(time)`. If `canRepair(time)` returns true, it means `time` is achievable, and we can try for an even smaller time. If it returns false, we need more time.

This sets up a classic binary search. We define a search space for the time, from a `low` of 0 to a `high` which is a safe upper bound (e.g., `100L * cars * cars`). We repeatedly check the middle of our search space, `mid`, and adjust the boundaries (`low` or `high`) based on the result of `canRepair(mid)` until we converge on the smallest possible time.

```java
class Solution {
    public long repairCars(int[] ranks, int cars) {
        long low = 0;
        // A safe upper bound: the mechanic with the highest possible rank (100)
        // repairs all cars. Using long to prevent overflow.
        long high = 100L * cars * cars;
        long ans = high;

        while (low <= high) {
            long mid = low + (high - low) / 2;
            if (canRepair(mid, ranks, cars)) {
                // This time is achievable, try for a smaller one.
                ans = mid;
                high = mid - 1;
            } else {
                // This time is not enough, need more time.
                low = mid + 1;
            }
        }
        return ans;
    }

    // Checks if it's possible to repair `cars` within the given `time`.
    private boolean canRepair(long time, int[] ranks, int cars) {
        long repairedCarsCount = 0;
        for (int rank : ranks) {
            // For a mechanic with rank `r`, time = r * n*n
            // => n*n = time / r
            // => n = sqrt(time / r)
            repairedCarsCount += (long) Math.sqrt((double) time / rank);
            // Optimization: if we can already repair enough cars, no need to check further.
            if (repairedCarsCount >= cars) {
                return true;
            }
        }
        return repairedCarsCount >= cars;
    }
}
```
### Algorithm
- The problem has a monotonic property: if all cars can be repaired within a given time `t`, they can certainly be repaired in any time `t' > t`. This allows us to use binary search on the answer (the minimum time).
- Define a search range for the time. A lower bound `low` can be `0`. A safe upper bound `high` can be the time taken by the worst mechanic (rank 100) to repair all cars alone, i.e., `100 * cars^2`. This value fits in a 64-bit integer (`long`).
- Implement a helper function, `canRepair(time)`, which returns `true` if it's possible to repair `cars` within the given `time`, and `false` otherwise.
  - Inside `canRepair(time)`, for each mechanic with rank `r`, calculate the number of cars they can repair: `n = floor(sqrt(time / r))`. 
  - Sum these values of `n` for all mechanics. If the total sum is `>= cars`, it's possible, so return `true`.
- Perform a binary search within the range `[low, high]`:
  - In each step, calculate `mid = low + (high - low) / 2`.
  - If `canRepair(mid)` is `true`, it means `mid` is a potential answer, and we might be able to do even better (in less time). So, we record `mid` as a possible answer and shrink the search space to the lower half: `high = mid - 1`.
  - If `canRepair(mid)` is `false`, the time `mid` is not enough. We need more time, so we search in the upper half: `low = mid + 1`.
- The search terminates when `low > high`, and the last recorded valid time is the minimum possible time.

# Solutions
### Java

```java
class Solution {
public
  long repairCars(int[] ranks, int cars) {
    long left = 0, right = 1L * ranks[0] * cars * cars;
    while (left < right) {
      long mid = (left + right) >> 1;
      long cnt = 0;
      for (int r : ranks) {
        cnt += Math.sqrt(mid / r);
      }
      if (cnt >= cars) {
        right = mid;
      } else {
        left = mid + 1;
      }
    }
    return left;
  }
}

```

### CPP

```cpp
class Solution {
public:
  long long repairCars(vector<int> &ranks, int cars) {
    long long left = 0, right = 1LL * ranks[0] * cars * cars;
    while (left < right) {
      long long mid = (left + right) >> 1;
      long long cnt = 0;
      for (int r : ranks) {
        cnt += sqrt(mid / r);
      }
      if (cnt >= cars) {
        right = mid;
      } else {
        left = mid + 1;
      }
    }
    return left;
  }
};

```

### Python

```python
class Solution:
    def repairCars(self, ranks: List[int], cars: int) -> int: def check(t: int) -> bool: return sum(int(sqrt(t // r)) for r in ranks) >= cars return bisect_left(range(ranks[0] * cars * cars), True, key=check)

```