Binary Search - Minimum Speed to Arrive on Time

You must ride n trains of distances dist[i]. All trains except the last depart at integer hours. Find the minimum integer speed to arrive on time (within `hour` hours). Return -1 if impossible.

Input: dist=[1,3,2], hour=6 → Output: 1

Input: dist=[1,3,2], hour=2.7 → Output: 3

Binary search on speed in [1, 10^7]. For a given speed, compute total time: sum(ceil(dist[i]/speed)) for all but last, plus dist[n-1]/speed for the last train.

lo=1, hi=10^7 (max constraint).
For mid speed: time = sum(ceil(dist[i]/mid)) for i
If time <= hour: hi=mid (try slower).
Else: lo=mid+1.
If even at max speed arrival is impossible, return -1.

class Solution { public int minSpeedOnTime(int[] dist, double hour) { int n = dist.length; if (hour <= n - 1) return -1; // can't make it regardless int lo = 1, hi = (int) 1e7; while (lo < hi) { int mid = lo + (hi - lo) / 2; double time = 0; for (int i = 0; i < n - 1; i++) time += (dist[i] + mid - 1) / mid; time += (double) dist[n - 1] / mid; if (time <= hour) hi = mid; else lo = mid + 1; } return lo; } }

Time Complexity: O(N log(10^7))
Space Complexity: O(1)