We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Speed to Arrive on Time

Difficulty: Medium

Problem Description

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 i-th train ride.

Each train can only depart at an integer hour, so you may need to wait in between each train ride. 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.

Key Insights

  • The speed must be a positive integer.
  • The total time taken must not exceed the given hour.
  • If the calculated time for the last train exceeds the available hour, it's impossible to reach on time.
  • A binary search can be used to efficiently find the minimum speed.

Space and Time Complexity

Time Complexity: O(n log(max_dist)) where n is the number of trains and max_dist is the maximum distance in the dist array.
Space Complexity: O(1) since we are using a constant amount of space.

Solution

The solution involves using binary search to find the minimum speed required to arrive on time. We will define a helper function to calculate the total time taken by all trains at a given speed. The key points are:

  1. For each train ride, compute the time based on the current speed.
  2. If the time is not an integer, we need to round it up since we can only depart at integer hours.
  3. We perform binary search between 1 and a maximum speed (determined by the maximum distance divided by the minimum possible time).

Code Solutions

def minSpeedOnTime(dist, hour):
    def canArriveOnTime(speed):
        time = 0
        for i in range(len(dist) - 1):
            time += (dist[i] + speed - 1) // speed  # Ceiling division
        time += dist[-1] / speed  # Last train ride can take fractional time
        return time <= hour

    left, right = 1, 10**7
    result = -1
    while left <= right:
        mid = (left + right) // 2
        if canArriveOnTime(mid):
            result = mid
            right = mid - 1
        else:
            left = mid + 1
    return result
← Back to All Questions