Code Implementation

import math

class Solution:
    def minSpeedOnTime(self, dist, hour):
        left, right = 1, 10**7
        n = len(dist)
        res = -1
        while left <= right:
            mid = (left + right) // 2
            time = 0.0
            for i in range(n - 1):
                time += math.ceil(dist[i] / mid)
            time += dist[-1] / mid
            if time <= hour:
                res = mid
                right = mid - 1
            else:
                left = mid + 1
        return res
      

#include <vector>
#include <cmath>
using namespace std;

class Solution {
public:
    int minSpeedOnTime(vector<int>& dist, double hour) {
        int left = 1, right = 1e7, res = -1, n = dist.size();
        while (left <= right) {
            int mid = left + (right - left) / 2;
            double time = 0.0;
            for (int i = 0; i < n - 1; ++i)
                time += ceil((double)dist[i] / mid);
            time += (double)dist[n-1] / mid;
            if (time <= hour) {
                res = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return res;
    }
};
      

class Solution {
    public int minSpeedOnTime(int[] dist, double hour) {
        int left = 1, right = 10000000, res = -1, n = dist.length;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            double time = 0.0;
            for (int i = 0; i < n - 1; ++i)
                time += Math.ceil((double)dist[i] / mid);
            time += (double)dist[n-1] / mid;
            if (time <= hour) {
                res = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return res;
    }
}
      

/**
 * @param {number[]} dist
 * @param {number} hour
 * @return {number}
 */
var minSpeedOnTime = function(dist, hour) {
    let left = 1, right = 1e7, res = -1, n = dist.length;
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        let time = 0.0;
        for (let i = 0; i < n - 1; ++i)
            time += Math.ceil(dist[i] / mid);
        time += dist[n-1] / mid;
        if (time <= hour) {
            res = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return res;
};
      

Problem Description

You are given an array dist where dist[i] represents the distance of the i-th train ride, and a floating-point number hour representing the total time you have to arrive at your destination. You must take the train rides in order, and after each ride (except the last), you must wait until the next integer hour to depart (i.e., you can only depart at whole hours).

Your task is to find the minimum integer speed (in units per hour) such that you can complete all the rides within hour hours. If it is impossible to arrive on time, return -1.

• Each train can be driven at any positive integer speed.
• You cannot reuse or skip any ride.
• There is always at most one valid answer.

Thought Process

At first glance, we might consider simulating all possible speeds, checking for each if we can arrive on time. However, with the constraints (distances can be up to 10⁵ and the answer can be as high as 10⁷), brute-force is computationally expensive.

The main challenge comes from the "wait until the next integer hour" rule for each ride except the last. This means that for every ride except the last, we must round up the time spent to the next integer. This rounding introduces complexity in calculating the total travel time.

Since the answer must be the minimum integer speed that works, and the function mapping speed to travel time is monotonic (higher speed never increases travel time), we can use binary search to efficiently find the answer.

Solution Approach

• Step 1: Understand the Time Calculation
  • For each ride except the last, the time spent is ceil(dist[i] / speed) (since you must wait for the next integer hour).
  • For the last ride, you don't need to wait; the time is dist[last] / speed.
  • Add all these up to get the total time for a given speed.
• Step 2: Binary Search for the Minimum Speed
  • Set your search range for speed from 1 to 10⁷ (per constraints).
  • For each candidate speed, compute the total travel time using the logic above.
  • If the total time is less than or equal to hour, try a lower speed (move the right boundary).
  • If not, try a higher speed (move the left boundary).
  • Continue until you find the minimum speed that allows arrival on time, or determine it is impossible.
• Step 3: Implementation Details
  • Use integer division carefully and apply ceiling (ceil) where required.
  • Return -1 if no speed in the range works.

Example Walkthrough

Input: dist = [1, 3, 2], hour = 6

• Suppose we try speed = 1:
• First ride: ceil(1/1) = 1 hour
• Second ride: ceil(3/1) = 3 hours
• Last ride: 2/1 = 2 hours
• Total: 1 + 3 + 2 = 6 hours
• This matches the allowed hour exactly, so speed = 1 works.
• But let's say hour = 2.7:
• Try speed = 3:
• First ride: ceil(1/3) = 1 hour
• Second ride: ceil(3/3) = 1 hour
• Last ride: 2/3 ≈ 0.666... hour
• Total: 1 + 1 + 0.666... ≈ 2.666...
• This fits within 2.7 hours, so speed = 3 is the answer.

The binary search will efficiently find the minimum such speed.

Time and Space Complexity

• Brute-Force:
  • Try each speed from 1 up to 10⁷.
  • For each speed, sum up ride times in O(N).
  • Time Complexity: O(N * 10⁷) — too slow for large inputs.
• Optimized (Binary Search):
  • Binary search over speed from 1 to 10⁷: O(log(10⁷)).
  • For each candidate speed, compute total travel time in O(N).
  • Total Time Complexity: O(N log(10⁷))
  • Space Complexity: O(1) extra space (apart from input).

Summary

The key insight is to realize that the total time function is monotonic with respect to speed, enabling a binary search for the minimum speed. By carefully simulating the waiting rule (using ceiling for all but the last ride), we can efficiently determine the answer. This approach is both elegant and efficient, leveraging properties of monotonic functions and binary search to solve what would otherwise be an intractable problem.