{x}
blog image

Minimum Speed to Arrive on Time

You are given a floating-point number hour, representing the amount of time you have to reach the office. To commute to the office, you must take n trains in sequential order. You are also given an integer array dist of length n, where dist[i] describes the distance (in kilometers) of the ith train ride.

Each train can only depart at an integer hour, so you may need to wait in between each train ride.

  • For example, if the 1st train ride takes 1.5 hours, you must wait for an additional 0.5 hours before you can depart on the 2nd train ride at the 2 hour mark.

Return the minimum positive integer speed (in kilometers per hour) that all the trains must travel at for you to reach the office on time, or -1 if it is impossible to be on time.

Tests are generated such that the answer will not exceed 107 and hour will have at most two digits after the decimal point.

 

Example 1:

Input: dist = [1,3,2], hour = 6
Output: 1
Explanation: At speed 1:
- The first train ride takes 1/1 = 1 hour.
- Since we are already at an integer hour, we depart immediately at the 1 hour mark. The second train takes 3/1 = 3 hours.
- Since we are already at an integer hour, we depart immediately at the 4 hour mark. The third train takes 2/1 = 2 hours.
- You will arrive at exactly the 6 hour mark.

Example 2:

Input: dist = [1,3,2], hour = 2.7
Output: 3
Explanation: At speed 3:
- The first train ride takes 1/3 = 0.33333 hours.
- Since we are not at an integer hour, we wait until the 1 hour mark to depart. The second train ride takes 3/3 = 1 hour.
- Since we are already at an integer hour, we depart immediately at the 2 hour mark. The third train takes 2/3 = 0.66667 hours.
- You will arrive at the 2.66667 hour mark.

Example 3:

Input: dist = [1,3,2], hour = 1.9
Output: -1
Explanation: It is impossible because the earliest the third train can depart is at the 2 hour mark.

 

Constraints:

  • n == dist.length
  • 1 <= n <= 105
  • 1 <= dist[i] <= 105
  • 1 <= hour <= 109
  • There will be at most two digits after the decimal point in hour.

Solution Explanation: Minimum Speed to Arrive on Time

This problem asks to find the minimum positive integer speed at which a sequence of train rides can be completed within a given time limit (hour). Each train ride has a distance (dist[i]), and we must wait until the next full hour before departing on the next train.

The optimal approach is to use binary search. This is because the relationship between speed and travel time is monotonic: higher speeds lead to shorter travel times.

Algorithm:

  1. Feasibility Check: First, we check if the problem is even solvable. If the number of trains is greater than the total number of hours allowed (rounded up), it's impossible to arrive on time, and we return -1.

  2. Binary Search Setup: We perform a binary search within a reasonable range of speeds. The lower bound is 1 (minimum speed), and the upper bound can be a large value (e.g., 107 as specified in the problem constraints) or dynamically determined based on the maximum distance and time.

  3. check(speed) Function: This is a crucial helper function that determines if a given speed allows us to arrive on time. It iterates through each train ride, calculates the travel time (t = dist[i] / speed), and adds it to the total time. Crucially, for all but the last train, we use Math.ceil(t) to account for the waiting time until the next full hour.

  4. Binary Search Iteration: The binary search repeatedly narrows the search space. If check(mid) (where mid is the middle speed) returns true (we arrive on time), we update the right bound to mid. Otherwise, we update the left bound to mid + 1.

  5. Result: After the binary search converges, the left bound represents the minimum speed that allows arrival on time. If the left bound exceeds the upper limit, it means no suitable speed exists, and we return -1.

Time Complexity: O(N * log M), where N is the number of train rides, and M is the upper bound of the speed range (in the binary search). The check() function takes O(N) time, and the binary search takes O(log M) iterations.

Space Complexity: O(1), as we only use a few variables to store the search bounds and intermediate results. The space used is constant regardless of the input size.

Code Examples (Python):

import math
 
class Solution:
    def minSpeedOnTime(self, dist: List[int], hour: float) -> int:
        n = len(dist)
        if n > math.ceil(hour):
            return -1
 
        def check(speed):
            total_time = 0
            for i in range(n):
                time = dist[i] / speed
                total_time += math.ceil(time) if i < n - 1 else time
            return total_time <= hour
 
        left, right = 1, 10**7  # Adjust upper bound if necessary
        while left < right:
            mid = (left + right) // 2
            if check(mid):
                right = mid
            else:
                left = mid + 1
        return left if check(left) else -1

The code in other languages (Java, C++, Go, TypeScript, Rust, Javascript, Kotlin) follows the same algorithmic structure, differing only in syntax and specific library functions. They all implement binary search and the check() function to efficiently find the minimum speed.