2594. Minimum Time to Repair Cars

You are given an integer array ranks representing the ranks of mechanics. Each mechanic has a rank r which determines the time taken to repair cars: specifically, a mechanic with rank r takes r * n^2 minutes to repair n cars.

You must calculate the smallest possible amount of time needed to repair exactly cars cars using all available mechanics optimally.

Formally, given:

• An array of integers ranks, where ranks[i] is the rank of the i-th mechanic.
• An integer cars, representing the total number of cars to be repaired.

Determine the minimum time necessary to repair all cars, given mechanics work simultaneously.

• Mechanics repair cars simultaneously, each mechanic independently.

• Time taken by a mechanic of rank r to repair n cars is:

  time = r * n^2
  

• The relationship between the number of cars repaired and the total time is monotonic, making it suitable for a binary search solution.

To efficiently solve the problem, follow these steps clearly:

1. Establish Search Bounds
   • Lower bound: Set to 1 minute.
   • Upper bound: Set to max(ranks) * cars^2, representing the maximum time needed in the worst case.
2. Binary Search on Time
   • While the lower bound is less than or equal to the upper bound:
     1. Choose the midpoint (mid) as a candidate time.
     2. Check if it is possible to repair all cars within mid minutes:

        • For each mechanic with rank r, calculate how many cars can be repaired within mid minutes, using:

          cars_repaired = floor(sqrt(mid / r))
          

        • If the total number of cars repaired by all mechanics at mid minutes is at least cars, record mid as a candidate answer and search for a potentially smaller solution (set upper bound to mid - 1).
        • If not enough cars are repaired, search with a larger time (set lower bound to mid + 1).
3. Implement Feasibility Check
   • For each given time T, calculate how many cars all mechanics can collectively repair. If it meets or exceeds cars, the time T is feasible.
4. Return Final Answer
   • The binary search result gives the minimum feasible time required.

• Time Complexity: O(n * log(maxTime))
• Space Complexity: O(1)

Given:

• ranks = [4, 2, 3, 1]
• cars = 10

Example calculation:

• Mechanic 1 (rank 4): repairs 2 cars in 4 * 2^2 = 16 mins
• Mechanic 2 (rank 2) repairs 2 cars: 2 * 2^2 = 8 mins
• Mechanic 3 (rank 3) repairs 2 cars: 3 * 2^2 = 12 mins
• Mechanic 4 (rank 1) repairs 4 cars: 1 * 4^2 = 16 mins

Total cars repaired = 10. Minimum possible time is thus 16 minutes.

2025-03-16 Minimum Time to Repair Cars - LeetCode leetcode.com

Below is a clear outline for the JavaScript implementation:

/**
 * Calculates the minimum time required to repair all cars.
 * @param {number[]} ranks - An array of mechanic ranks.
 * @param {number} cars - The total number of cars that need repairs.
 * @return {number} The minimum time required.
 */
function repairCars(ranks, cars) {
    const log = typeof NestedInteger !== 'undefined' ? () => {} : console.log;
    const table = typeof NestedInteger!== 'undefined' ? () => {} : console.table;

    log(`Initial ranks='${ranks}'; cars='${cars}'`);

    const slowestRank = Math.max(...ranks);
    log('slowestRank=', slowestRank);

    const highestTime = slowestRank * cars * cars;
    log('highestTime=', highestTime);

    function canRepair(time, ranks, cars) {
        let totalCars = 0;
        for (let i = 0; i < ranks.length; i++) {
            const carsByRankPerMinute = Math.floor(Math.sqrt(time / ranks[i]));
            totalCars += carsByRankPerMinute;
        }
        return totalCars >= cars;
    }

    const p1 = [5, ranks, cars];
    log(`canRepair(${p1}) = ${canRepair.apply(this, p1)}`);

    //function bs()
    let low = 0;
    let high = highestTime;

    let result = high;

    while (low <= high) {
        const mid = Math.floor((low + high) / 2);
        const can = canRepair(mid, ranks, cars);
        if (can) {
            log(`=== more optimal. new mid='${mid}'; old result = '${result}'`);
            result = mid;
            high = mid - 1;

        } else {

            low = mid + 1;
        }
    }

    return result;
}

// Test cases
const testCases = [
    { ranks: [4, 2, 3, 1], cars: 10, expected: 16 },
    { ranks: [5,1,8], cars: 6, expected: 16 },

];

testCases.forEach((test, index) => {
    const result = repairCars(test.ranks, test.cars);
    console.log(`Test Case ${index + 1}: ${result === test.expected ? 'Passed' : 'Failed'} (Expected: ${test.expected}, Got: ${result})`);
});