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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Speed to Arrive on Time

Number: 2000

Difficulty: Medium

Paid? No

Companies: Amazon, Google

Problem Description

Given an array of distances for a sequence of train rides and a total allowed time (hour), determine the minimum positive integer speed (in kilometers per hour) required to arrive at your destination on time. Each train (except the last one) must wait until the next integer hour before departing, which adds waiting time when the ride finishes mid-hour. If it is impossible to arrive on time, return -1.

Key Insights

  • The waiting time for each train (except the last) is calculated by taking the ceiling of the ride duration.
  • The total travel time is the sum of the rounded-up times for all rides except the last ride plus the exact time for the last ride.
  • A binary search on the possible speeds (from 1 to 10^7) is effective since the answer is guaranteed to be within this range.
  • At each potential speed, compute the total travel time and compare it to the allowed hour.
  • If the computed time is less than or equal to hour, try a lower speed; otherwise, increase the speed.

Space and Time Complexity

Time Complexity: O(n * log(maxSpeed)) where n is the number of trains and maxSpeed is 10^7. Space Complexity: O(1)

Solution

We use binary search to find the minimum speed that allows arrival on time:

  1. Set low to 1 and high to 10^7.
  2. For each mid value (candidate speed), calculate the total travel time:
    • For each train ride except the last, use the ceiling of (dist[i] / speed) to account for waiting until the next integer hour.
    • For the last train, add the exact time (dist[last] / speed).
  3. If the total time is less than or equal to the allowed hour, keep track of the candidate speed and try to lower the speed by adjusting the high pointer.
  4. Otherwise, move the low pointer to try a higher speed.
  5. If no valid speed is found, return -1.

Data structures used:

  • A simple loop for iterating over the distance array.
  • Variables for the binary search (low, high, mid) to narrow down the answer.

Algorithmic approach:

  • Binary Search: Efficiently narrows down the potential speed that meets the time constraint.
  • Math operations: Uses ceiling computation to manage waiting times for intermediate rides.

Key gotchas:

  • Ensure that waiting time is only applied for the trains that are not the last ride.
  • Handle the precision of floating-point operations properly during time calculations.

Code Solutions

# Python solution for the Minimum Speed to Arrive on Time problem

import math

def minSpeedOnTime(dist, hour):
    # Helper function to check if the given speed allows arriving on time
    def can_arrive_on_time(speed):
        total_time = 0.0
        n = len(dist)
        # Iterate over all rides except the last ride
        for i in range(n - 1):
            # Calculate time taken for the ride and round up to the next integer
            total_time += math.ceil(dist[i] / speed)
        # For the last ride, use the exact fraction
        total_time += dist[-1] / speed
        return total_time <= hour

    low, high = 1, 10**7
    result = -1

    # Binary search for the minimum speed
    while low <= high:
        mid = (low + high) // 2  # Candidate speed
        if can_arrive_on_time(mid):
            result = mid  # Candidate speed works, try to find a smaller one
            high = mid - 1
        else:
            low = mid + 1

    return result

# Example usage:
print(minSpeedOnTime([1, 3, 2], 6))    # Output: 1
print(minSpeedOnTime([1, 3, 2], 2.7))  # Output: 3
print(minSpeedOnTime([1, 3, 2], 1.9))  # Output: -1
← Back to All Questions