2594. Minimum Time to Repair Cars - Medium

前往題目

想法

• 猜答案，二元搜尋

思路

1. 二元搜尋分鐘數，範圍是最小可能到最大可能
2. 計算以當前分鐘數來看可以修多少台車
3. 比目標少，就增加分鐘；比目標多就減少分鐘數
4. 最後收斂的位置就是答案

Code

class Solution {
    public long repairCars(int[] ranks, int cars) {
        long l = 0, r = (long)1e14;
        long mid = 0;
        long res = -1;

        // Binary search to guess the answer
        while (l <= r) {
            mid = l + (r - l) / 2;

            long repairedCars = 0;

            // Cal. total cars can be repaired in mid minutes
            for (int rank : ranks) {
                repairedCars += Math.sqrt(mid / rank); // Cars this rank can repair
            }

            // Valid
            if (repairedCars >= cars) {
                res = mid;
                r = mid - 1;
            } else { // invalid, need more time
                l = mid + 1;
            }
        }

        return res;
    }
}

▶

有瑕疵的code

這裡直接用分鐘來看但是WA了

class Solution {
    public long repairCars(int[] ranks, int cars) {
        long l = 0L, r = 100 * 1000000 * 1000000;
        long mid = 0L;

        // Binary search to guess the answer
        while (l < r) {
            mid = l + (r - l) / 2;

            // Check if the minimum time is valid
            long maxTimeToRepair = Long.MIN_VALUE;
            for (int rank : ranks) {
                long repairTime = rank * cars * cars;
                // Update the minimum time to repair all the cars
                maxTimeToRepair = Math.max(repairTime, maxTimeToRepair);
            }

            // Valid
            if (mid > maxTimeToRepair) {
                r = mid - 1;
            } else if (mid < maxTimeToRepair) { // Invalid, not enough time to repair
                l = mid + 1;
            }
        }

        return l;
    }
}