Minimum Speed to Arrive on Time

Find the smallest speed that lets you reach the office before the deadline.

binary-search simulation math

You must commute to work using a train that makes several trips. You are given a list `dist` of positive integers: `dist[i]` is the distance (in miles) of the i-th trip. The train's speed is the same for all trips and can be any **positive integer** (miles per hour). For all trips except the last one, the train must wait for the next departure, which takes exactly 1 hour after the trip ends. That is, the time for a non-final trip of distance `d` at speed `s` is `ceil(d / s)`, and after that you wait 1 hour before the next trip starts. The final trip takes `d / s` hours (no extra waiting). You need to arrive at the office in at most `hour` hours (a floating-point number).

Implement the function `min_speed_on_time(dist, hour)` that returns the **minimum integer speed** `s` (>= 1) that allows you to arrive on time. If it is impossible to arrive on time even with an arbitrarily large speed, return `-1`.

**Notes:**
- `ceil(d / s)` means the smallest integer greater than or equal to `d / s`.
- The total travel time is the sum of the times of all trips (including the 1-hour waits after non-final trips).
- The speed must be a positive integer.

**Input:**
- `dist`: a list of positive integers, length 1 to 1000, each between 1 and 10^5.
- `hour`: a float, 1.0 <= hour <= 10^9, with at most two decimal places.

**Output:**
- Return an integer: the minimum speed, or -1 if impossible.

**Complexity:** Your solution should handle the maximum constraints in O(n log M) time, where M is a reasonable upper bound for speed (e.g., 10^7).

Constraints

1 <= len(dist) <= 1000; 1 <= dist[i] <= 10^5; 1.0 <= hour <= 10^9 (hour has at most two decimal places). The answer, if it exists, will not exceed 10^7.

Example

>>> min_speed_on_time([1,3,2], 6)
1
>>> min_speed_on_time([1,3,2], 2.7)
3
>>> min_speed_on_time([1,3,2], 1.9)
-1

25 points ~30 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

If a given speed s works, then any larger speed also works — use binary search on s.

Compute total time for speed s as sum(math.ceil(d / s) for d in dist[:-1]) + dist[-1] / s.

Binary search from low=1 to high=10**7, checking if total_time <= hour. If even the maximum speed fails, return -1.

Be careful with floating-point precision when comparing total time to hour; use a small epsilon like 1e-9.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.