Binary Search for the RESCUE 🛟
IntuitionThe goal is to determine the minimum time required so that the combined work of all mechanics repairs at least the specified number of cars. Each mecha
# **Intuition**
The goal is to determine the minimum time required so that the combined work of all mechanics repairs at least the specified number of cars. Each mechanic with rank r can repair n cars in r * n^2 minutes. For a given time t, we can calculate the maximum number of cars a mechanic can repair by rearranging the formula as:n = sqrt(t/r)
By summing up the cars repaired by each mechanic, we can check if the total meets or exceeds the target.

# **Approach**
Define the Search Range:
• The minimum time (l) is 0.
• The maximum time (h) is estimated by the worst-case scenario, i.e., the mechanic with the highest rank repairing all cars:
h = max(ranks) * cars^2.
Binary Search:
• Calculate the middle time m = l + (h - l) / 2.
• For each mechanic, compute the number of cars they can repair in m minutes using sqrt(m / r) and sum these values.
• If the total number of cars repaired is greater than or equal to cars, then mis a valid candidate, and we try to lower the time by setting
h = m - 1.
• Otherwise, increase the time by setting l = m + 1.
Result:
• Continue this process until the search range is exhausted. The minimum valid time is stored in ans.
Complexity
# **Time complexity:**
`O(n x log(maxTime))`,where n is the number of mechanics and maxTime is roughly max(ranks) x cars^2.

# **Space complexity:**
`O(1)` extra space, aside from the input.

# Code
```cpp []
class Solution {
public:
    long long repairCars(vector<int>& ranks, int cars) {
        int n = ranks.size();
        long long low = 1, high = (long long)*max_element(ranks.begin(), ranks.end()) * cars * cars, mid;
        long long ans = high;

        auto isFeasible = [&](long long time) {
            int repaired = 0;
            for(auto rank : ranks)
            {
                repaired += floor(sqrt(time / rank));
                if(repaired >= cars)
                    return true;
            }
            return false;
        };

        while(low < high)
        {
            mid = (low + high) / 2;
            if(isFeasible(mid))
            {
                high = mid;
                ans = min(ans, high);
            }
            else
                low = mid + 1;
        }
        return ans;
    }
};
```
['Binary Search', 'C++']