Find the smallest integer train speed that lets you reach the destination within the allowed time, accounting for whole-hour departures between intermediate trips.
You are given a sequence of train ride distances and a total time limit. You may choose one positive integer speed for all rides. Each ride takes distance / speed hours, but for every ride except the last one, the departure to the next ride can only happen at the next integer hour, so the ride time is rounded up to the next whole hour.
Your task is to return the minimum integer speed that allows the total travel time to be less than or equal to the given limit. If no such speed exists, return -1.
This is a classic "search on the answer" problem: as speed increases, total time never increases.
Input Format
distances: an array of positive integers, wheredistances[i]is the distance for the -th ride.hour: a positive real number representing the maximum allowed total travel time.
Interpretation:
- For rides
0ton-2, each ride time is rounded up to the next integer hour. - The last ride uses its exact fractional travel time.
Output Format
Return the minimum positive integer speed such that the total time is at most hour, or -1 if it is impossible.
Constraints
1 <= distances.length1 <= distances[i]hour > 0- The answer, if it exists, is an integer speed.
- Infeasibility can occur when
houris too small to fit the mandatory integer-hour rounding on intermediate rides.
Example 1
Input
distances = [1,3,2], hour = 6
Output
1
Explanation
At speed 1, the times are ceil(1/1) + ceil(3/1) + 2/1 = 1 + 3 + 2 = 6, which fits exactly. No smaller positive speed exists.
Example 2
Input
distances = [1,3,2], hour = 2.7
Output
3
Explanation
At speed 3, the time is ceil(1/3) + ceil(3/3) + 2/3 = 1 + 1 + 0.666... = 2.666..., which is within the limit. Speed 2 gives 1 + 2 + 1 = 4, which is too slow.
Show 1 more example
Example 3
Input
distances = [1,3,2], hour = 1.9
Output
-1
Explanation
The first two rides alone require at least 2 whole hours because of rounding, so it is impossible to finish within 1.9 hours.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.