Minimum speed to arrive on time

Array Binary Search

47.7% acceptance

Feb 25, 2026

2448

292

You are given a floating-point number hour, representing the amount of time you have to reach the office. You must take n trains in sequential order. Return the minimum positive integer speed for you to arrive on time, or -1 if impossible.

Solution

Rust

Time O(n log n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn min_speed_on_time(dist: Vec<i32>, hour: f64) -> i32 {
    let n = dist.len();
    // Impossible if n-1 >= hour (need at least n-1 integer waits)
    if (n as f64 - 1.0) >= hour {
      return -1;
    }

    // Use hour * 100 as integer to avoid float issues
    let hour100 = (hour * 100.0).round() as i64;

    let can_make = |speed: i64| -> bool {
      let mut total100 = 0i64;
      for i in 0..n - 1 {
        // ceil(dist[i] / speed) * 100
        total100 += ((dist[i] as i64 + speed - 1) / speed) * 100;
        if total100 >= hour100 { return false; }
      }
      let remaining100 = hour100 - total100;
      // last train: dist[n-1] / speed <= remaining100 / 100
      // i.e., dist[n-1] * 100 <= speed * remaining100
      dist[n - 1] as i64 * 100 <= speed * remaining100
    };

    let mut lo = 1i64;
    let mut hi = 10_000_000i64;
    while lo < hi {
      let mid = (lo + hi) / 2;
      if can_make(mid) { hi = mid; } else { lo = mid + 1; }
    }
    lo as i32
  }
}