Minimum skips to arrive at meeting on time

Array Dynamic Programming

38.8% acceptance

Feb 25, 2026

353

You are given hoursBefore hours to travel n roads. After each road except the last, you must rest until the next integer hour (or skip the rest). Return the minimum number of skips required to arrive on time, or -1 if impossible.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn min_skips(dist: Vec<i32>, speed: i32, hours_before: i32) -> i32 {
    let n = dist.len();
    let spd = speed as i64;
    let limit = hours_before as i64 * spd;

    // dp[j] = min time (in distance units, not divided by speed)
    // with j skips to reach end of current road
    let inf = i64::MAX / 2;
    let mut dp = vec![inf; n + 1];
    dp[0] = 0;

    for i in 0..n {
      let d = dist[i] as i64;
      let mut new_dp = vec![inf; n + 1];
      for j in 0..=i {
        if dp[j] == inf { continue; }
        // Option 1: don't skip after road i (no rest needed after last road)
        if i < n - 1 {
          let t = dp[j] + d;
          let rounded = ((t + spd - 1) / spd) * spd;
          if rounded < new_dp[j] { new_dp[j] = rounded; }
        } else {
          // Last road: no rest needed
          let t = dp[j] + d;
          if t < new_dp[j] { new_dp[j] = t; }
        }
        // Option 2: skip rest after road i
        if j < n {
          let t = dp[j] + d;
          if t < new_dp[j + 1] { new_dp[j + 1] = t; }
        }
      }
      dp = new_dp;
    }

    for j in 0..=n {
      if dp[j] <= limit {
        return j as i32;
      }
    }
    -1
  }
}