LeetCode Ts-2594. Minimum Time to Repair Cars

    AllenLi
    CodingLeetCode Js-Binary Search

    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.

    你有一個整數陣列 ranks，表示一些技師的等級。ranks[i] 是第 i 個技師的等級。
等級 r 的技師修理 n 輛車需要的時間為 r * n2。
你還有一個整數 cars，表示車庫裡面等待修理的汽車總數。
請回傳修理完所有汽車所需的最短時間。
注意：所有技師可以同時修車。

    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.​​​​​

    Solution:
    這題我們可以用 binary search 搜尋最短時間，
    left 為最小時間，right 為最慢的技師修理完所有車的時間。
    透過中間值 mid 計算每個技師在該時間內最多能修幾台車，
    如果總數 >= cars 就嘗試更短時間，
    否則需要更多時間，迴圈結束後回傳 right。

    Code 1: BigO(n log cars)

    function repairCars(ranks: number[], cars: number): number {
    let left = 0;
    let right = Math.min(...ranks) * cars * cars + 1;

    while (right - left > 1) {
        const mid = Math.floor((left + right) / 2);
        let repaired = 0;

        for (const r of ranks) {
            repaired += Math.floor(Math.sqrt(mid / r));
            if (repaired >= cars) break; 
        }

        if (repaired >= cars) {
            right = mid;
        } else {
            left = mid;  
        }
    }
    return right; 
};

    FlowChart:
    Example 1

    Input: ranks = [4,2,3,1], cars = 10

mid 50
r of ranks 4 repaired 3
r of ranks 2 repaired 8
r of ranks 3 repaired 12
right = mid 50

mid 25
r of ranks 4 repaired 2
r of ranks 2 repaired 5
r of ranks 3 repaired 7
r of ranks 1 repaired 12
right = mid 25

mid 12
r of ranks 4 repaired 1
r of ranks 2 repaired 3
r of ranks 3 repaired 5
r of ranks 1 repaired 8
left = mid 12

mid 18
r of ranks 4 repaired 2
r of ranks 2 repaired 5
r of ranks 3 repaired 7
r of ranks 1 repaired 11
right = mid 18

mid 15
r of ranks 4 repaired 1
r of ranks 2 repaired 3
r of ranks 3 repaired 5
r of ranks 1 repaired 8
left = mid 15

mid 16
r of ranks 4 repaired 2
r of ranks 2 repaired 4
r of ranks 3 repaired 6
r of ranks 1 repaired 10
right = mid 16

return right; // 16

    Example 2

    Input: ranks = [5,1,8], cars = 6

mid 18
r of ranks 5 repaired 1
r of ranks 1 repaired 5
r of ranks 8 repaired 6
right = mid 18

mid 9
r of ranks 5 repaired 1
r of ranks 1 repaired 4
r of ranks 8 repaired 5
left = mid 9

mid 13
r of ranks 5 repaired 1
r of ranks 1 repaired 4
r of ranks 8 repaired 5
left = mid 13

mid 15
r of ranks 5 repaired 1
r of ranks 1 repaired 4
r of ranks 8 repaired 5
left = mid 15

mid 16
r of ranks 5 repaired 1
r of ranks 1 repaired 5
r of ranks 8 repaired 6
right = mid 16

return right; // 16

    Related Posts