Problem

You are given an integer hoursBefore, the number of hours you have to travel to your meeting. To arrive at your meeting, you have to travel through n roads. The road lengths are given as an integer array dist of length n, where dist[i] describes the length of the ith road in kilometers. In addition, you are given an integer speed, which is the speed (in km/h) you will travel at.

After you travel road i, you must rest and wait for the next integer hour before you can begin traveling on the next road. Note that you do not have to rest after traveling the last road because you are already at the meeting.

  • For example, if traveling a road takes 1.4 hours, you must wait until the 2 hour mark before traveling the next road. If traveling a road takes exactly 2 hours, you do not need to wait.

However, you are allowed to skip some rests to be able to arrive on time, meaning you do not need to wait for the next integer hour. Note that this means you may finish traveling future roads at different hour marks.

  • For example, suppose traveling the first road takes 1.4 hours and traveling the second road takes 0.6 hours. Skipping the rest after the first road will mean you finish traveling the second road right at the 2 hour mark, letting you start traveling the third road immediately.

Return theminimum number of skips required to arrive at the meeting on time, or -1 if it isimpossible.

Examples

Example 1

1
2
3
4
5
6

Input: dist = [1,3,2], speed = 4, hoursBefore = 2
Output: 1
Explanation:
Without skipping any rests, you will arrive in (1/4 + 3/4) + (3/4 + 1/4) + (2/4) = 2.5 hours.
You can skip the first rest to arrive in ((1/4 + _0_) + (3/4 + 0)) + (2/4) = 1.5 hours.
Note that the second rest is shortened because you finish traveling the second road at an integer hour due to skipping the first rest.

Example 2

1
2
3
4
5

Input: dist = [7,3,5,5], speed = 2, hoursBefore = 10
Output: 2
Explanation:
Without skipping any rests, you will arrive in (7/2 + 1/2) + (3/2 + 1/2) + (5/2 + 1/2) + (5/2) = 11.5 hours.
You can skip the first and third rest to arrive in ((7/2 + _0_) + (3/2 + 0)) + ((5/2 + _0_) + (5/2)) = 10 hours.

Example 3

1
2
3

Input: dist = [7,3,5,5], speed = 1, hoursBefore = 10
Output: -1
Explanation: It is impossible to arrive at the meeting on time even if you skip all the rests.

Constraints

  • n == dist.length
  • 1 <= n <= 1000
  • 1 <= dist[i] <= 10^5
  • 1 <= speed <= 10^6
  • 1 <= hoursBefore <= 10^7

Solution

Method 1 – Dynamic Programming (Min Skips)

Intuition

We use DP to track the minimum total time for each number of skips. For each road, we can either wait for the next integer hour or skip the rest. We want the minimum skips such that the total time is within hoursBefore.

Approach

Let dp[i][k] be the minimum total time to finish the first i roads with k skips. For each road, we can either round up to the next integer hour (no skip) or not (skip). Use integer math to avoid floating point errors.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include <vector>
#include <algorithm>
class Solution {
public:
    int minSkips(vector<int>& dist, int speed, int hoursBefore) {
        int n = dist.size();
        vector<long> dp(n+1, 0);
        for (int i = 0; i < n; ++i) {
            vector<long> ndp(n+1, LONG_MAX);
            for (int k = 0; k <= i; ++k) {
                // No skip: round up
                long t = ((dp[k] + dist[i] + speed - 1) / speed) * speed;
                ndp[k] = min(ndp[k], t);
                // Skip: no round up
                if (k+1 <= n) ndp[k+1] = min(ndp[k+1], dp[k] + dist[i]);
            }
            dp = ndp;
        }
        for (int k = 0; k <= n; ++k) {
            if (dp[k] <= (long)hoursBefore * speed) return k;
        }
        return -1;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

import "math"
func minSkips(dist []int, speed, hoursBefore int) int {
    n := len(dist)
    dp := make([]int64, n+1)
    for i := 0; i < n; i++ {
        ndp := make([]int64, n+1)
        for k := range ndp { ndp[k] = math.MaxInt64 }
        for k := 0; k <= i; k++ {
            t := ((dp[k]+int64(dist[i])+int64(speed)-1)/int64(speed))*int64(speed)
            if t < ndp[k] { ndp[k] = t }
            if k+1 <= n && dp[k]+int64(dist[i]) < ndp[k+1] {
                ndp[k+1] = dp[k]+int64(dist[i])
            }
        }
        dp = ndp
    }
    for k := 0; k <= n; k++ {
        if dp[k] <= int64(hoursBefore)*int64(speed) { return k }
    }
    return -1
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

import java.util.*;
class Solution {
    public int minSkips(int[] dist, int speed, int hoursBefore) {
        int n = dist.length;
        long[] dp = new long[n+1];
        for (int i = 0; i < n; i++) {
            long[] ndp = new long[n+1];
            Arrays.fill(ndp, Long.MAX_VALUE);
            for (int k = 0; k <= i; k++) {
                long t = ((dp[k]+dist[i]+speed-1)/speed)*speed;
                ndp[k] = Math.min(ndp[k], t);
                if (k+1 <= n) ndp[k+1] = Math.min(ndp[k+1], dp[k]+dist[i]);
            }
            dp = ndp;
        }
        for (int k = 0; k <= n; k++) {
            if (dp[k] <= (long)hoursBefore*speed) return k;
        }
        return -1;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    fun minSkips(dist: IntArray, speed: Int, hoursBefore: Int): Int {
        val n = dist.size
        var dp = LongArray(n+1)
        for (i in 0 until n) {
            val ndp = LongArray(n+1) { Long.MAX_VALUE }
            for (k in 0..i) {
                val t = ((dp[k]+dist[i]+speed-1)/speed)*speed
                ndp[k] = minOf(ndp[k], t)
                if (k+1 <= n) ndp[k+1] = minOf(ndp[k+1], dp[k]+dist[i])
            }
            dp = ndp
        }
        for (k in 0..n) {
            if (dp[k] <= hoursBefore.toLong()*speed) return k
        }
        return -1
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
    def minSkips(self, dist: list[int], speed: int, hoursBefore: int) -> int:
        n = len(dist)
        dp = [0] * (n+1)
        for i in range(n):
            ndp = [float('inf')] * (n+1)
            for k in range(i+1):
                t = ((dp[k]+dist[i]+speed-1)//speed)*speed
                ndp[k] = min(ndp[k], t)
                if k+1 <= n:
                    ndp[k+1] = min(ndp[k+1], dp[k]+dist[i])
            dp = ndp
        for k in range(n+1):
            if dp[k] <= hoursBefore*speed:
                return k
        return -1
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

impl Solution {
    pub fn min_skips(dist: Vec<i32>, speed: i32, hours_before: i32) -> i32 {
        let n = dist.len();
        let mut dp = vec![0i64; n+1];
        for i in 0..n {
            let mut ndp = vec![i64::MAX; n+1];
            for k in 0..=i {
                let t = ((dp[k]+dist[i] as i64+speed as i64-1)/speed as i64)*speed as i64;
                ndp[k] = ndp[k].min(t);
                if k+1 <= n {
                    ndp[k+1] = ndp[k+1].min(dp[k]+dist[i] as i64);
                }
            }
            dp = ndp;
        }
        for k in 0..=n {
            if dp[k] <= hours_before as i64 * speed as i64 {
                return k as i32;
            }
        }
        -1
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    minSkips(dist: number[], speed: number, hoursBefore: number): number {
        const n = dist.length;
        let dp = Array(n+1).fill(0);
        for (let i = 0; i < n; i++) {
            const ndp = Array(n+1).fill(Infinity);
            for (let k = 0; k <= i; k++) {
                const t = Math.ceil((dp[k]+dist[i])/speed)*speed;
                ndp[k] = Math.min(ndp[k], t);
                if (k+1 <= n) ndp[k+1] = Math.min(ndp[k+1], dp[k]+dist[i]);
            }
            dp = ndp;
        }
        for (let k = 0; k <= n; k++) {
            if (dp[k] <= hoursBefore*speed) return k;
        }
        return -1;
    }
}

Complexity

  • ⏰ Time complexity: O(n^2) — DP for each road and skip count.
  • 🧺 Space complexity: O(n) — For DP arrays.