2187.minimum-time-to-complete-trips.md

2187. Minimum Time to Complete Trips

常搞不清楚換算？把題目給定的條件「單位」寫出來。題目給定一趟旅程所需時間 = time[i] 時間 / 趟，給定時間 t，可以換算成總共可以完成 t / time[i] 次旅程，因為 時間 / (時間 / 趟) = 趟。

Linear Search

Given a time t, then the number of trips that can be completed is t / time[i]. We can start from the minimum speed 1, and check if it's possible to complete all trips within the given time. If not, we check 2, then 3, and so on until we found the time that can complete all trips.

// t / time[i] = # trips >= totalTrips?
t = 1
1/1 + 1/2 + 1/3 = 1 + 0 + 0 = 1 < 5

t = 2
2/1 + 2/2 + 2/3 = 2 + 1 + 0 = 3 < 5

t = 3
3/1 + 3/2 + 3/3 = 3 + 1 + 1 = 5 >= 5

// -------------------------
totalTrips = 5
time = [1, 2, 3]
// The total trips that can be completed within the current time
t = 1   1  0  0 = 1  < 5   X
t = 2   2  1  0 = 3  < 5   X
t = 3   3  1  1 = 5  >= 5  O
t = 4   4  2  1 = 7  >= 5  O
t = 5   5  2  1 = 8  >= 5  O
t = 6   6  3  2 = 11 >= 5  O

fun minimumTime(time: IntArray, totalTrips: Int): Long {
    var requiredTime = 1L
    var trips = 0
    while (trips < totalTrips) {
        trips = 0
        for (t in time) {
            trips += requiredTime / t
        }
        if (totalTrips <= trips) break
        requiredTime++
    }
    return requiredTime
}

Binary Search

We can optimize the linear search solution with some modifications based on some key observations:

Monotonicity

• If time = t is sufficient, then any time > t is also sufficient.
• If time = t is not sufficient, then any time < t is also not sufficient.

This exhibits the monotonicity characteristic, the search space can be reduced efficiently by applying binary search. We can use binary search to find the minimum time: We're looking for the first element that satisfies the condition: totalTrips <= trips.

// required time
 1  2  3  4  5  6  7, ...
[X, X, X, O, O, O, O]
          ^ // The minimum time to complete all trips

时间越多，可以完成的旅途總次數也就越多，有单调性，可以二分答案。

Lower Bound

• The minimum possible required time must at at least 1. A better lower bound is min(time) because the fastest bus will complete one trip in that time. Let's take an example:

time = [3, 5, 7]
totalTrips = 12

• The fastest bus will complete one trip in 3 time.
• The absolute minimum time to complete all trips cannot be less than 3. Because the fastest bus will complete one trip in 3 time, it's impossible to complete all trips (which is 12) in less than 3 time.

Upper Bound

The maximum time is min(time) * totalTrips, why? Let's take the same example above:

• If only the fastest bus is available in the worst case, then completing all trips will take 3 * 12 = 36 time. Now we have more buses available, so the time will be less than 36.
• Or simply using 10^7 from the problem constraints (not recommended).

fun minimumTime(time: IntArray, totalTrips: Int): Long {
    val totalTrips = totalTrips.toLong()
    var min = Long.MAX_VALUE
    for (t in time) {
        min = minOf(min, t)
    }

    var left = 1L
    var right = min * totalTrips
    while (left <= right) {
        val middle = left + (right - left) / 2
        val isValid = totalTrips <= getTotalTrips(time, middle)
        if (isValid) {
            right = middle - 1
        } else {
            left = middle + 1
        }
    }
    return left
}

private fun getTotalTrips(times: IntArray, requiredTime: Long): Long {
    var totalTrips = 0L
    for (t in times) {
        totalTrips += requiredTime / t.toLong()
    }
    return totalTrips
}

• Time Complexity: O(n * log m), where n is the size of the time array, and m is the maximum time to complete all trips.
• Space Complexity: O(1).