Minimum Speed to Arrive on Time

Share

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.

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

Solution Approach

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