1870.minimum-speed-to-arrive-on-time.md

1870. Minimum Speed to Arrive on Time

Linear Search

We're finding the minimum speed to reach the office on time. Let's start from speed 1, and check if it's possible to reach the office within hour hours. If not, we increase the speed by 1 and check again.

speed = distance / time
time = distance / speed

s = 1
[1, 3, 2]
ceil(1/1) + ceil(3/1) + 2/1 = 6 <= 6

s = 2
ceil(1/2) + ceil(3/2) + 2/2 = 1 + 2 + 1 = 4

s = 3
ceil(1/3) + ceil(3/3) + 2/3 = 1 + 1 + 0.66 = 2.66 <= 6

fun minSpeedOnTime(dist: IntArray, hour: Double): Int {
    var speed = 1
    while (speed <= 10000000) {
        // See below for the implementation of getTotalHours()
        if (getTotalHours(dist, speed) <= hour) return speed
        speed++
    }
    return -1
}

Binary Search

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

1. The minimum speed is 1, and the maximum speed is the maximum of possible value, which is 10^7 (based on the problem constraints).
2. As we increase the speed, the time to reach the office is shorter, and vice versa. This exhibits the monotonicity characteristic, so we can use binary search to find the minimum speed: We're looking for the first element that satisfies the condition: getTotalHours(dist, middle) <= hour.

It's a little bit confused why we don't ceil the last distance, maybe just skip it.

fun minSpeedOnTime(dist: IntArray, hour: Double): Int {
    val min = 1
    val max = 10000000

    var left = min
    var right = max
    while (left <= right) {
        val middle = left + (right - left) / 2
        val isValid = getTotalHours(dist, middle) <= hour

        // Find the first element that meets the condition (can reach the office)
        if (isValid) {
            right = middle - 1
        } else {
            left = middle + 1
        }
    }
    // We check if the left is in the range, if not, return -1
    return if (left in min..max) left else -1
    // Or
    // return if (left > max) -1 else left
}

// We calculate the total hours to reach the office with the given speed.
// ceil(dist[0] / speed) + ceil(dist[1] / speed) + ... + ceil(dist[n - 2] / speed) + dist[n - 1] / speed
// The last distance doesn't need to wait, so we don't need to ceil it.
private fun getTotalHours(dist: IntArray, speed: Int): Double {
    var hours = 0.0
    // We iterate all distances except the last one: because we have to wait if the hour is not an integer.
    for (d in 0 until dist.size - 1) {
        hours += Math.ceil(dist[d].toDouble() / speed) // If the hour is 1.5, then total hours is 2.
    }
    // We add the last distance to the total hours, which we don't have to wait.
    hours += dist[dist.size - 1].toDouble() / speed
    return hours
}

• Time Complexity: O(n * log m), where n is the size of the dist and m is the maximum speed.
• Space Complexity: O(1).