#1870 Minimum Speed to Arrive on Time - Solution

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.

For example, if the 1^st train ride takes 1.5 hours, you must wait for an additional 0.5 hours before you can depart on the 2^nd 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 10⁷ 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 <= 10⁵
1 <= dist[i] <= 10⁵
1 <= hour <= 10⁹
There will be at most two digits after the decimal point in hour.

The key challenge in #1870 Minimum Speed to Arrive on Time is determining the smallest integer speed that allows you to complete all train rides within a given time limit. Since the travel time decreases as speed increases, the problem exhibits a monotonic property, making it well suited for Binary Search.

Instead of testing every possible speed, define a search range (for example from 1 to a large upper bound). For each candidate speed, compute the total travel time across all segments. Every segment except the last must be rounded up using ceil(distance / speed) because trains can only depart at integer hours. The final segment can use the exact fractional time.

If the calculated time is within the allowed hour, try smaller speeds; otherwise increase the speed. This narrowing process efficiently finds the minimum feasible speed. The approach runs in O(n log M) time, where n is the number of distances and M is the maximum speed range, while using O(1) extra space.

Approach	Time Complexity	Space Complexity
Binary Search on Speed	O(n log M)	O(1)

Solutions (6)

Binary Search Approach

Idea: To find the minimum positive integer speed that allows you to reach the office in the given time, you can use binary search on the speed. Initialize the left boundary to 1 (minimum speed) and right boundary to a large number (e.g., 10^7, as specified in the problem statement), then narrow down the possible speed by simulating the commute.

Steps:

Perform binary search on speed from 1 to 10^7.
For each candidate speed, iterate over all trains, compute the total time taken, rounding up the time taken for all but the last train.
If total time is less than or equal to given hour, try with a smaller speed. Otherwise, try with a larger speed.

If you narrow down to a result, it is the minimum speed required. If search is exhausted without finding a valid speed, return -1.

Time Complexity: O(n log k), where n is the number of train distances and k is the maximum speed (10^7).
Space Complexity: O(1), as the solution does not require any extra space beyond a fixed set of variables.

C C++Java Python C#JavaScript

1using System;
2public class Solution {
3    public int MinSpeedOnTime(int[] dist, double hour) {
4        int left = 1, right = 10000000;
5        while (left < right) {
6            int mid = (left + right) / 2;
7            double time = 0.0;
8            for (int i = 0; i < dist.Length; ++i) {
9                if (i < dist.Length - 1) {
10                    time += Math.Ceiling((double)dist[i] / mid);
11                } else {
                    time += (double)dist[i] / mid;
                }
            }
            if (time <= hour) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left == 10000000 ? -1 : left;
    }

    public static void Main() {
        int[] dist = {1, 3, 2};
        double hour = 6;
        Console.WriteLine(new Solution().MinSpeedOnTime(dist, hour));
    }
}

Explanation

The C# solution employs binary search to find the minimum speed that trains can travel while fulfilling the given hour constraint. Integer and double arithmetic enable accurate calculations for time consideration and speed adjustment.