Minimum Skips to Arrive at Meeting On Time

Hard

#1719Time: O(n^2), where n is the number of roads. We have two nested loops, both iterating up to `n`.Space: O(n^2), where n is the number of roads. This is for the 2D `dp` table of size `n x n`.

Patterns

Dynamic Programming

Data structures

Array

Prompt

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 i^th 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 the minimum number of skips required to arrive at the meeting on time, or -1 if it is impossible.

Example 1:

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:

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:

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⁵
1 <= speed <= 10⁶
1 <= hoursBefore <= 10⁷

Approaches

2 approaches with complexity analysis and trade-offs.

This problem can be modeled using dynamic programming. We can define a state dp[i][j] that represents the minimum possible arrival time at the start of road i having used exactly j skips. By iterating through each road and considering the two choices at each rest stop (skip or wait), we can build up a solution. The final answer is the minimum j for which the total travel time is within the hoursBefore limit.

Algorithm

Define a 2D DP array, dp[i][j], to store the minimum start time for road i using j skips.
To avoid floating-point precision issues, we work with 'distance' units (time * speed) and use long integers. So, dp[i][j] will store the minimum start 'distance' for road i with j skips.
Initialize dp table of size n x n with a very large value, representing infinity. Set dp[0][0] = 0, as we start at time 0 before the first road with 0 skips.
Iterate from road i = 0 to n-2. For each road, iterate through the possible number of skips j from 0 to i.
For each state dp[i][j], calculate the finish 'distance' after traveling road i: finish_dist = dp[i][j] + dist[i].
From this finish_dist, determine the two possible start 'distances' for the next road i+1: a. No skip: The start 'distance' is ceil(finish_dist / speed) * speed. This is calculated using integer arithmetic as ((finish_dist + speed - 1) / speed) * speed. b. Skip: The start 'distance' is simply finish_dist.
Update the dp table for road i+1:
- dp[i+1][j] = min(dp[i+1][j], no_skip_start_dist)
- dp[i+1][j+1] = min(dp[i+1][j+1], skip_start_dist)
After filling the dp table, iterate through the number of skips j from 0 to n-1.
For each j, calculate the final arrival 'distance' after the last road: total_dist = dp[n-1][j] + dist[n-1].
If total_dist is less than or equal to hoursBefore * speed, then j is a possible number of skips. The first such j we find is the minimum required, so we return it.
If the loop completes without finding a solution, it's impossible to arrive on time. Return -1.

Walkthrough

We use a 2D array, dp[i][j], where i is the road index (from 0 to n-1) and j is the number of skips used (from 0 to i). To avoid floating-point precision errors, we can work with integer 'distances' by multiplying all time values by speed. So, dp[i][j] will store the minimum 'distance' traveled to be ready to start road i, using j skips.

The base case is dp[0][0] = 0, meaning we are at the start of the first road at time 0. We then iterate from road i = 0 to n-2. For each road, we calculate the finish 'distance' and then update the possible start 'distances' for the next road, i+1. If we don't skip the rest, the time is rounded up to the next integer hour, which corresponds to ceil(finish_dist / speed) * speed. If we do skip, the start time for the next road is immediate.

After computing all states up to the start of the last road (dp[n-1]), we can find the total travel 'distance' for each possible number of skips. We then check which is the smallest number of skips j that allows finishing within hoursBefore * speed 'distance' units.

1import java.util.Arrays;2 3class Solution {4    public int minSkips(int[] dist, int speed, int hoursBefore) {5        int n = dist.length;6        long[][] dp = new long[n][n];7        for (int i = 0; i < n; i++) {8            Arrays.fill(dp[i], Long.MAX_VALUE);9        }10 11        dp[0][0] = 0;12 13        for (int i = 0; i < n - 1; i++) {14            long travelDist = dist[i];15            for (int j = 0; j <= i; j++) {16                if (dp[i][j] == Long.MAX_VALUE) {17                    continue;18                }19 20                // Option 1: Don't skip the rest after road i21                long finishDist = dp[i][j] + travelDist;22                long nextStartNoSkip = (finishDist + speed - 1) / speed * speed;23                dp[i + 1][j] = Math.min(dp[i + 1][j], nextStartNoSkip);24 25                // Option 2: Skip the rest after road i26                long nextStartSkip = finishDist;27                if (j + 1 < n) {28                    dp[i + 1][j + 1] = Math.min(dp[i + 1][j + 1], nextStartSkip);29                }30            }31        }32 33        long maxAllowedDist = (long) hoursBefore * speed;34 35        for (int j = 0; j < n; j++) {36            if (dp[n - 1][j] != Long.MAX_VALUE) {37                long totalDist = dp[n - 1][j] + dist[n - 1];38                if (totalDist <= maxAllowedDist) {39                    return j;40                }41            }42        }43 44        return -1;45    }46}

Complexity

Time

O(n^2), where n is the number of roads. We have two nested loops, both iterating up to `n`.

Space

O(n^2), where n is the number of roads. This is for the 2D `dp` table of size `n x n`.

Trade-offs

Pros

The DP state and transitions are logical and directly model the problem.
Using integer arithmetic for 'distance' avoids potential floating-point precision issues, making the solution robust.

Cons

The space complexity of O(n^2) can be high for large n (up to 1000), potentially leading to memory issues.

This approach is a space-optimized version of the 2D dynamic programming solution. By observing that the calculation for the current road's minimum times only depends on the results from the immediately preceding road, we can reduce the space complexity from O(n^2) to O(n). We maintain only the DP states for the current and next roads, discarding older states that are no longer needed.

Algorithm

The core logic is the same as the 2D DP approach, but we optimize space.
Observe that to compute the DP values for road i+1, we only need the values from road i. This means we don't need to store the entire 2D table.
We can use two 1D arrays, one for the current road's start times (dp) and one for the next road's start times (next_dp).
Initialize a 1D array dp of size n with dp[0] = 0 and others as infinity. This represents the start 'distances' for road 0.
Iterate from road i = 0 to n-2. In each iteration, create a next_dp array.
Loop through skips j from 0 to i. Based on dp[j], calculate the two possible start 'distances' for road i+1 (with and without a skip) and update next_dp[j] and next_dp[j+1] accordingly.
After the inner loop, replace dp with next_dp for the next iteration.
After iterating through all rests, the final dp array will hold the minimum start 'distances' for the last road (n-1).
The final check for the minimum number of skips is the same as in the previous approach: find the smallest j such that dp[j] + dist[n-1] <= hoursBefore * speed.

Walkthrough

Instead of a 2D dp table, we use a 1D array, dp, of size n. dp[j] will store the minimum start 'distance' for the current road i using j skips.

We start with dp representing the start times for road 0, which is dp[0] = 0 and infinity for all other j. Then, we iterate from i = 0 to n-2. In each iteration, we compute a next_dp array which will hold the start 'distances' for road i+1. The transition logic is identical to the 2D DP approach. After computing all possible start times for road i+1, we assign next_dp to dp and proceed to the next road.

This way, we only ever store the DP states for two adjacent roads at any time, reducing the space requirement to O(n). The final step of checking the dp array (which now holds start times for the last road) against hoursBefore remains the same.

An initial check can be performed: if the total distance divided by speed (the time taken if all rests are skipped) is greater than hoursBefore, it's impossible to arrive on time. This can handle some edge cases early.

1import java.util.Arrays;2 3class Solution {4    public int minSkips(int[] dist, int speed, int hoursBefore) {5        int n = dist.length;6        // An optional initial check for impossibility.7        long totalDistSum = 0;8        for (int d : dist) {9            totalDistSum += d;10        }11        if ((double) totalDistSum / speed > hoursBefore) {12            return -1;13        }14 15        long[] dp = new long[n];16        Arrays.fill(dp, Long.MAX_VALUE);17        dp[0] = 0;18 19        for (int i = 0; i < n - 1; i++) {20            long travelDist = dist[i];21            long[] next_dp = new long[n];22            Arrays.fill(next_dp, Long.MAX_VALUE);23 24            for (int j = 0; j <= i; j++) {25                if (dp[j] == Long.MAX_VALUE) {26                    continue;27                }28 29                // Option 1: Don't skip the rest after road i30                long finishDist = dp[j] + travelDist;31                long nextStartNoSkip = (finishDist + speed - 1) / speed * speed;32                next_dp[j] = Math.min(next_dp[j], nextStartNoSkip);33 34                // Option 2: Skip the rest after road i35                long nextStartSkip = finishDist;36                if (j + 1 < n) {37                    next_dp[j + 1] = Math.min(next_dp[j + 1], nextStartSkip);38                }39            }40            dp = next_dp;41        }42 43        long maxAllowedDist = (long) hoursBefore * speed;44 45        for (int j = 0; j < n; j++) {46            if (dp[j] != Long.MAX_VALUE) {47                long totalDist = dp[j] + dist[n - 1];48                if (totalDist <= maxAllowedDist) {49                    return j;50                }51            }52        }53 54        return -1;55    }56}

Complexity

Time

O(n^2), where n is the number of roads. The nested loops structure remains the same as the 2D DP approach.

Space

O(n), where n is the number of roads. We use two 1D arrays of size `n` to store DP states for the current and next roads.

Trade-offs

Pros

Significantly more memory-efficient than the 2D DP approach, making it feasible for larger constraints on n.
Maintains the same O(n^2) time complexity, which is efficient enough for the given constraints.

Cons

The time complexity remains O(n^2), so it's not faster for very large n.

Solutions

Solution

1class Solution {2public3  int minSkips(int[] dist, int speed, int hoursBefore) {4    int n = dist.length;5    double[][] f = new double[n + 1][n + 1];6    for (int i = 0; i <= n; i++) {7      Arrays.fill(f[i], 1 e20);8    }9    f[0][0] = 0;10    double eps = 1 e - 8;11    for (int i = 1; i <= n; ++i) {12      for (int j = 0; j <= i; ++j) {13        if (j < i) {14          f[i][j] = Math.min(f[i][j], Math.ceil(f[i - 1][j]) +15                                          1.0 * dist[i - 1] / speed - eps);16        }17        if (j > 0) {18          f[i][j] =19              Math.min(f[i][j], f[i - 1][j - 1] + 1.0 * dist[i - 1] / speed);20        }21      }22    }23    for (int j = 0; j <= n; ++j) {24      if (f[n][j] <= hoursBefore + eps) {25        return j;26      }27    }28    return -1;29  }30}

1class Solution {2public:3  int minSkips(vector<int> &dist, int speed, int hoursBefore) {4    int n = dist.size();5    vector<vector<double>> f(n + 1, vector<double>(n + 1, 1e20));6    f[0][0] = 0;7    double eps = 1e-8;8    for (int i = 1; i <= n; ++i) {9      for (int j = 0; j <= i; ++j) {10        if (j < i) {11          f[i][j] =12              min(f[i][j], ceil(f[i - 1][j] + dist[i - 1] * 1.0 / speed - eps));13        }14        if (j) {15          f[i][j] = min(f[i][j], f[i - 1][j - 1] + dist[i - 1] * 1.0 / speed);16        }17      }18    }19    for (int j = 0; j <= n; ++j) {20      if (f[n][j] <= hoursBefore + eps) {21        return j;22      }23    }24    return -1;25  }26};

1class Solution:2    def minSkips(self, dist: List[int], speed: int, hoursBefore: int) -> int: n = len(dist) f = [[inf] * (n + 1) for _ in range(n + 1)] f[0][0] = 0 eps = 1e-8 for i, x in enumerate(dist, 1): for j in range(i + 1): if j < i: f[i][j] = min(f[i][j], ceil(f[i - 1][j] + x / speed - eps)) if j: f[i][j] = min(f[i][j], f[i - 1][j - 1] + x / speed) for j in range(n + 1): if f[n][j] <= hoursBefore + eps: return j return - 1

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem