Leetcode 2549 - Minimum Time to Repair Cars

Link to problem

Description

You are given an integer array ranks representing the ranks of some mechanics. ranks$_\text{i}$ is the rank of the i$^\text{th}$ mechanic. A mechanic with a rank r can repair n cars in r * n^2 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.

Solution

Think this problem as two subproblems:

1. If a given time is sufficient for mechanics to fix all cars.
2. Binary search to find the lowest time required to fix the cars.

For 1., the cars that a mechanic with rank r in time could fix is $\sqrt{\text{time}/r}$ cars. The maximum of cars that the mechanics could fix could be obtained easily by summing up the numbers.

Implementation

class Solution {
public:

    bool isPossibleInTime(const vector<int>& ranks, int cars, long long time) {
        long long maxCars = 0;
        for (auto i: ranks) {
            maxCars += static_cast<int>(sqrt(time / i));
        }
        return maxCars >= cars;
    }

    long long repairCars(vector<int>& ranks, int cars) {
        long long minTime = 1;
        long long maxTime = (long long)cars * cars * ranks.front();
        long long mid = (maxTime + minTime) / 2;

        while (maxTime > minTime) {
            if (isPossibleInTime(ranks, cars, mid)) {
                maxTime = mid;
            }
            else {
                minTime = mid + 1;
            }
            mid = (maxTime + minTime) / 2;
        }

        return mid;
    }
};