🔗 🟡 2187. Minimum Time to Complete Trips 1641

tags: `Weekly Contest 282` `陣列(Array)` `二分搜尋(Binary Search)`

題意

給定一個陣列 $time$ ，其中 $time[i]$ 表示第 $i$ 輛公車完成 一次旅程 所需的時間。

每輛公車可以連續完成多趟旅程，也就是說，一輛公車當前旅程完成後，可以 立即開始 下一趟旅程。每輛公車獨立運行，也就是說可以同時有多輛公車在運行且互不影響。

給定一個整數 $totalTrips$ ，表示所有公車總共應完成的旅程數。返回完成至少 $totalTrips$ 旅程所需的最少時間。

約束條件

$1 \leq \text{time.length} \leq 10^5$
$1 \leq \text{time[i]}, \text{totalTrips} \leq 10^7$

思路：二分搜尋(Binary Search)

首先不難發現，當時間 $t$ 越大，所有公車完成的旅程數越多，因此答案具有 單調性 ，可以對答案進行二分搜尋(Binary Search) 來找到最小的時間。

因此我們可以定義一個函數 check(t) 來檢查在時間 $t$ 內是否能完成至少 $totalTrips$ 次旅程。對於第 $i$ 輛公車，其在時間 $t$ 內最多能完成 $\lfloor \frac{t}{time_i} \rfloor$ 次旅程，因此我們只需要將所有公車的完成旅程數相加後，與 $totalTrips$ 比較即可。若 $\displaystyle (\sum_{i=0}^{n-1} \lfloor \frac{t}{time_i} \rfloor) \geq totalTrips$ ，則代表在時間 $t$ 內能完成至少 $totalTrips$ 次旅程，返回 $True$ ；否則返回 $False$ 。

接著確定二分搜尋的範圍，由於至少需要 $1$ 單位時間完成一次旅程，因此左界為 $1$ ；由於最多需要 $\text{time}$ 陣列中的最小值乘以 $totalTrips$ 才能完成所有旅程，因此可以令右界為 $\min(\text{time}) \times totalTrips$ 。

這裡使用閉區間的寫法，因此 while 迴圈的條件為 left <= right。在二分搜尋結束後， $right$ 會指向最大的不滿足條件的時間，而 $left$ 會指向最小的滿足條件的時間，因此答案為 $left$ 。

複雜度分析

時間複雜度： $\mathcal{O}(\log(D))$ ，其中 $D = \min(\text{time}) \times totalTrips$ 為二分搜尋的範圍
空間複雜度： $\mathcal{O}(1)$

class Solution:
    def minimumTime(self, time: List[int], totalTrips: int) -> int:
        def check(t):
            return sum(t // x for x in time) >= totalTrips

        left, right = 1, min(time) * totalTrips
        while left <= right:
            mid = (left + right) // 2
            if check(mid):
                right = mid - 1
            else:
                left = mid + 1
        return left

class Solution {
public:
    long long minimumTime(vector<int>& time, int totalTrips) {
        function<bool(long long)> check = [&](long long t) -> bool {
            long long sum = 0;
            for (int x : time) {
                sum += t / x;
            }
            return sum >= totalTrips;
        };
        long long left = 1;
        long long right = (long long) *min_element(time.begin(), time.end()) * totalTrips;
        while (left <= right) {
            long long mid = (left + right) / 2;
            if (check(mid)) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
};