Minimum Speed to Arrive on Time Problem

Problem

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.

Examples

Example 1:

1
2
3
4
5
6
7
8
9

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:

1
2
3
4
5
6
7
8
9

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:

1
2
3
4
5

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.

Solution

Method 1 – Binary Search

Intuition

We want to find the minimum integer speed such that the total travel time (including waiting for integer hour departures) does not exceed the given hour. Since the answer is monotonic (higher speed never increases travel time), we can use binary search over possible speeds.

Approach

  1. Set the search range for speed from 1 to a large upper bound (e.g., 10^7).
  2. For each candidate speed, simulate the total travel time:
    • For all but the last train, round up the time for each segment to the next integer (since you must wait for the next integer hour).
    • For the last train, add the exact time (no waiting).
  3. If the total time is within hour, try a lower speed; otherwise, try a higher speed.
  4. Return the minimum speed found, or -1 if impossible.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

#include <vector>
#include <cmath>
using namespace std;
class Solution {
public:
	int minSpeedOnTime(vector<int>& dist, double hour) {
		int left = 1, right = 1e7, ans = -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) left = mid + 1;
			else {
				ans = mid;
				right = mid - 1;
			}
		}
		return ans;
	}
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

import "math"
func minSpeedOnTime(dist []int, hour float64) int {
	left, right, ans := 1, 10000000, -1
	n := len(dist)
	for left <= right {
		mid := left + (right-left)/2
		time := 0.0
		for i := 0; i < n-1; i++ {
			time += math.Ceil(float64(dist[i]) / float64(mid))
		}
		time += float64(dist[n-1]) / float64(mid)
		if time > hour {
			left = mid + 1
		} else {
			ans = mid
			right = mid - 1
		}
	}
	return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

public int minSpeedOnTime(int[] dist, double hour) {
	int n = dist.length;
	int left = 1, right = 10000000, ans = -1;
	while (left <= right) {
		int mid = left + (right - left) / 2;
		double time = 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) left = mid + 1;
		else {
			ans = mid;
			right = mid - 1;
		}
	}
	return ans;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
	fun minSpeedOnTime(dist: IntArray, hour: Double): Int {
		var left = 1
		var right = 10000000
		var ans = -1
		val n = dist.size
		while (left <= right) {
			val mid = left + (right - left) / 2
			var time = 0.0
			for (i in 0 until n - 1) {
				time += kotlin.math.ceil(dist[i].toDouble() / mid)
			}
			time += dist[n - 1].toDouble() / mid
			if (time > hour) {
				left = mid + 1
			} else {
				ans = mid
				right = mid - 1
			}
		}
		return ans
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

import math
class Solution:
	def minSpeedOnTime(self, dist: list[int], hour: float) -> int:
		left, right, ans = 1, 10**7, -1
		n = len(dist)
		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:
				left = mid + 1
			else:
				ans = mid
				right = mid - 1
		return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

impl Solution {
	pub fn min_speed_on_time(dist: Vec<i32>, hour: f64) -> i32 {
		let (mut left, mut right, mut ans) = (1, 10_000_000, -1);
		let n = dist.len();
		while left <= right {
			let mid = left + (right - left) / 2;
			let mut time = 0.0;
			for i in 0..n - 1 {
				time += (dist[i] as f64 / mid as f64).ceil();
			}
			time += dist[n - 1] as f64 / mid as f64;
			if time > hour {
				left = mid + 1;
			} else {
				ans = mid;
				right = mid - 1;
			}
		}
		ans
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

function minSpeedOnTime(dist: number[], hour: number): number {
	let left = 1, right = 1e7, ans = -1;
	const n = dist.length;
	while (left <= right) {
		const mid = Math.floor(left + (right - left) / 2);
		let time = 0;
		for (let i = 0; i < n - 1; ++i) {
			time += Math.ceil(dist[i] / mid);
		}
		time += dist[n - 1] / mid;
		if (time > hour) left = mid + 1;
		else {
			ans = mid;
			right = mid - 1;
		}
	}
	return ans;
}

Complexity

  • ⏰ Time complexity: O(n log M), where n is the number of train rides and M is the upper bound for speed (e.g., 10^7). For each binary search step, we check all train rides.
  • 🧺 Space complexity: O(1), as only a constant amount of extra space is used.