題目資訊

• 題目編號: 2594
• 題目連結: Minimum Time to Repair Cars
• 主題: Array, Binary Search

題目敘述

你有一個整數數組 ranks，代表一些技工的等級。$ranks_i$ 是第 $i$ 位技工的等級。等級為 r 的技工可以在 $r \cdot n^2$ 分鐘內修理 $n$ 輛車。

你也得到一個整數 cars，代表等待在車庫中修理的汽車總數。

返回修理所有汽車所需的最短時間。

注意： 所有技工可以同時修理汽車。

範例 1:

輸入: ranks = [4,2,3,1], cars = 10
輸出: 16
解釋: 
- 第一位技工會修理兩輛車。需要的時間是 $4 \cdot 2 \cdot 2 = 16$ 分鐘。
- 第二位技工會修理兩輛車。需要的時間是 $2 \cdot 2 \cdot 2 = 8$ 分鐘。
- 第三位技工會修理兩輛車。需要的時間是 $3 \cdot 2 \cdot 2 = 12$ 分鐘。
- 第四位技工會修理四輛車。需要的時間是 $1 \cdot 4 \cdot 4 = 16$ 分鐘。
可以證明車輛無法在少於 16 分鐘內修理完畢。​​​​​

範例 2:

輸入: ranks = [5,1,8], cars = 6
輸出: 16
解釋: 
- 第一位技工會修理一輛車。需要的時間是 $5 \cdot 1 \cdot 1 = 5$ 分鐘。
- 第二位技工會修理四輛車。需要的時間是 $1 \cdot 4 \cdot 4 = 16$ 分鐘。
- 第三位技工會修理一輛車。需要的時間是 $8 \cdot 1 \cdot 1 = 8$ 分鐘。
可以證明車輛無法在少於 16 分鐘內修理完畢。​​​​​

約束條件:

• $1 \leq ranks.length \leq 10^5$
• $1 \leq ranks[i] \leq 100$
• $1 \leq cars \leq 10^6$

直覺

這個問題涉及一組具有特定等級的技工，以及一組需要維修的車輛。修理一輛車所需的時間取決於技工的等級以及他們維修的車輛數量。為了找到修理所有車輛所需的最短時間，我們需要有效地在技工之間分配維修任務，同時考慮到他們因等級不同而造成的效率差異。直覺上，如果我們能夠管理這些修理任務，使得所有車輛在最短的時間內完成修理，那麼我們需要透過最佳化地平衡技工之間的工作負荷來確定這個最短時間。

解法

這個解法運用了二分搜尋策略，並結合一個輔助函數來檢查是否能夠在給定時間內修理所有車輛。

1. 初始設置:

   • 首先，我們為二分搜尋確定一個初始跳躍大小。這個跳躍大小是根據技工列表中的最小等級乘以車輛總數的平方來計算的，這提供了一個由速度最快的技工在工作最大限度下估算的修理時間上限。

2. 二分搜尋策略:

   • 我們使用二分搜尋來確定所需的最短時間。二分搜尋的運作方式是通過在驗證在當前時間估計（minTime + jump）內修理所有車輛的可行性之後漸進地將跳躍大小減半。
   • 我們最初將 minTime 設置為 -1，一個小於任何可能有效時間的值。
   • 在每次迭代中，我們使用一個輔助函數來驗證是否可以在當前估計時間（minTime + jump）內修理所有車輛。如果不可行，這意味著我們當前的時間估計太小，我們需要通過當前跳躍大小來增加 minTime。
   • 如果可行，我們將跳躍大小減半，從而更精確地縮小可能的最短時間範圍。

3. 輔助函數:

   • 這個函數檢查是否能夠在給定的時間 t 內修理所有車輛。它計算每位技工可以修理的車輛數量，方式是確定一個最大整數 $n$，使得 $\text{rank} \times n^2 \leq t$。這個整數可以通過 $n = \sqrt{t / \text{rank}}$ 來確定。
   • 對於每位技工，函數從總車輛中減去他們可以修理的車輛數。如果在任何時候所有車輛都得到了照顧（不論是剛好或者超出），函數返回 true，表示 t 是一個可行的時間。否則，返回 false。

4. 結果計算:

   • 當跳躍大小變為零時，這標誌著二分搜尋的結束，也就是說我們找到了可以修理所有車輛的最短時間。由於 minTime 是在條件剛剛變得不可行時才增加的，minTime + 1 被作為答案返回，代表在可行的車輛修理計劃中準確需要的最短時間。

這種方法通過二分搜尋有效地縮小了解決方案空間，並依靠技工的等級來最佳化車輛修理的分配，從而在給定的約束下達成了一個高效的解決方案。

程式碼

C++

class Solution {
public:
    // 幫助函數用於檢查是否可以在時間 t 內修理所有車輛
    bool check(const vector<int>& ranks, int cars, long long t) {
        for(int rank : ranks) {
            // 計算當前技師可以修理的車輛數量
            cars -= static_cast<long long>(sqrt(t / rank));
            // 如果所有車輛都被修理，返回 true
            if(cars <= 0) return true;
        }
        // 如果無法在時間 t 內修理所有車輛，返回 false
        return false;
    }

    long long repairCars(vector<int>& ranks, int cars) {
        long long minTime = -1;

        // 根據最小的等級確定初始的跳躍大小
        long long jump = static_cast<long long>(*min_element(ranks.begin(), ranks.end())) * cars * cars;

        // 使用二分搜尋法逐步減半跳躍大小
        while(jump > 0) {
            // 不斷增加 minTime 直到無法在 minTime + jump 內修理車輛
            while(!check(ranks, cars, minTime + jump)) {
                minTime += jump;
            }
            // 將跳躍大小減半
            jump >>= 1;
        }

        // minTime + 1 是修理所有車輛所需的最小時間
        return minTime + 1;
    }
};

Python

class Solution:

    # 檢查是否能在時間 t 內修理所有車輛的輔助函數
    def check(self, ranks, cars, t):
        for rank in ranks:
            # 計算當前技工可以修理的車輛數量
            cars -= int((t / rank) ** 0.5)
            # 如果所有車輛都已修理，返回 True
            if cars <= 0:
                return True
        # 如果無法在時間 t 內修理所有車輛，返回 False
        return False

    def repairCars(self, ranks, cars):
        minTime = -1

        # 根據最低等級確定初始跳躍大小
        jump = min(ranks) * cars * cars

        # 透過不斷減半的方式進行二分搜尋
        while jump > 0:
            # 不斷增加 minTime，直到無法在 minTime + jump 修理完車輛
            while not self.check(ranks, cars, minTime + jump):
                minTime += jump
            # 將跳躍大小減半
            jump >>= 1

        # minTime + 1 是修理所有車輛所需的最少時間
        return minTime + 1

複雜度分析

• 時間複雜度: 演算法的時間複雜度為 $O(n \log(\text{maxRank} \cdot \text{cars}^2))$，其中 $n$ 是機械師的數量（即 ranks 向量的大小），maxRank 是 ranks 陣列中的最大值。這是因為對時間進行的二分搜尋需要 $O(\log(\text{max possible time}))$ 次迭代，並且在每次迭代中，check 函數被調用，其複雜度為 $O(n)$，因為它會遍歷每個機械師的等級。

• 空間複雜度: 演算法的空間複雜度為 $O(1)$，因為演算法使用恒定量的額外空間，與輸入大小無關。計算和檢查使用的是基本資料類型，並不需要隨著輸入大小擴展的額外資料結構。rank 向量的儲存不包括在內，因為它被認為是輸入的一部分。