- 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.

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

Set the search range for speed from 1 to a large upper bound (e.g., 10^7).
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).
If the total time is within hour, try a lower speed; otherwise, try a higher speed.
Return the minimum speed found, or -1 if impossible.

Code

[{"language":"C++","code":"#include <vector>\n#include <cmath>\nusing namespace std;\nclass Solution {\npublic:\n\tint minSpeedOnTime(vector<int>& dist, double hour) {\n\t\tint left = 1, right = 1e7, ans = -1, n = dist.size();\n\t\twhile (left <= right) {\n\t\t\tint mid = left + (right - left) / 2;\n\t\t\tdouble time = 0.0;\n\t\t\tfor (int i = 0; i < n - 1; ++i)\n\t\t\t\ttime += ceil((double)dist[i] / mid);\n\t\t\ttime += (double)dist[n - 1] / mid;\n\t\t\tif (time > hour) left = mid + 1;\n\t\

Related Tags