Minimum Speed to Arrive on Time

Minimum Speed to Arrive on Time

What is this problem about?

The Minimum Speed to Arrive on Time problem gives you a list of train ride distances and an hour limit. Each train ride except the last must take a whole number of hours (you wait for the next departure). Find the minimum integer speed such that all rides are completed within the given time. This Minimum Speed to Arrive on Time coding problem is a clean binary search on the answer application.

Why is this asked in interviews?

Apple, Amazon, and Google ask this because it is an excellent example of binary search on the answer — where you search over possible speed values and check feasibility. The array and binary search interview pattern is the key technique, and the ceiling arithmetic for wait times tests implementation precision.

Algorithmic pattern used

Binary search on speed in the range [1, max_possible_speed]. For a given speed s, compute total time: for each ride except the last, time = ceil(dist / s). For the last ride: dist / s (exact fraction). If total time ≤ hoursBefore, speed s is sufficient — try lower. Otherwise try higher. Binary search finds the minimum feasible speed.

Example explanation

Distances: [1, 3, 2], hoursBefore = 6.

• Speed = 1: time = ceil(1/1) + ceil(3/1) + 2/1 = 1 + 3 + 2 = 6 ≤ 6. Feasible.
• Try lower. Speed cannot be < 1 (minimum is 1).
• Minimum speed = 1.

Distances: [1, 3, 2], hoursBefore = 2.9.

• Speed = 2: ceil(0.5)+ceil(1.5)+1 = 1+2+1 = 4 > 2.9. Not feasible.
• Speed = 5: ceil(0.2)+ceil(0.6)+0.4 = 1+1+0.4 = 2.4 ≤ 2.9. Feasible.
• Binary search finds minimum = 5.

Common mistakes candidates make

• Applying ceil to the last ride (it should be exact division, not ceiling).
• Not detecting the impossible case: if n ≥ hoursBefore (not enough full hours even at infinite speed).
• Binary search bounds too narrow — speed can need to be very large.
• Integer overflow when speed × distance calculations get large.

Interview preparation tip

Binary search on the answer is a powerful technique for optimization problems. The key is recognizing a monotonic feasibility condition: if speed s works, all speeds > s also work. Practice identifying this monotonicity in problems about speeds, capacities, and thresholds. Equally important: implement the ceil function cleanly as (a + b - 1) / b in integer arithmetic instead of relying on floating-point library functions.