# Minimum Skips to Arrive at Meeting On Time
**Difficulty:** HARD
[External](https://leetcode.com/problems/minimum-skips-to-arrive-at-meeting-on-time)
Canonical: https://scaleengineer.com/dsa/problems/minimum-skips-to-arrive-at-meeting-on-time
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array
---
## 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 _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] <= 105`
* `1 <= speed <= 106`
* `1 <= hoursBefore <= 107`

# Approaches
## Dynamic Programming with 2D Array
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.
**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`.
**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.
### Explanation
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.

```java
import java.util.Arrays;

class Solution {
    public int minSkips(int[] dist, int speed, int hoursBefore) {
        int n = dist.length;
        long[][] dp = new long[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(dp[i], Long.MAX_VALUE);
        }

        dp[0][0] = 0;

        for (int i = 0; i < n - 1; i++) {
            long travelDist = dist[i];
            for (int j = 0; j <= i; j++) {
                if (dp[i][j] == Long.MAX_VALUE) {
                    continue;
                }

                // Option 1: Don't skip the rest after road i
                long finishDist = dp[i][j] + travelDist;
                long nextStartNoSkip = (finishDist + speed - 1) / speed * speed;
                dp[i + 1][j] = Math.min(dp[i + 1][j], nextStartNoSkip);

                // Option 2: Skip the rest after road i
                long nextStartSkip = finishDist;
                if (j + 1 < n) {
                    dp[i + 1][j + 1] = Math.min(dp[i + 1][j + 1], nextStartSkip);
                }
            }
        }

        long maxAllowedDist = (long) hoursBefore * speed;

        for (int j = 0; j < n; j++) {
            if (dp[n - 1][j] != Long.MAX_VALUE) {
                long totalDist = dp[n - 1][j] + dist[n - 1];
                if (totalDist <= maxAllowedDist) {
                    return j;
                }
            }
        }

        return -1;
    }
}
```
### Algorithm
1. Define a 2D DP array, `dp[i][j]`, to store the minimum start time for road `i` using `j` skips.
2. 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.
3. 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.
4. Iterate from road `i = 0` to `n-2`. For each road, iterate through the possible number of skips `j` from `0` to `i`.
5. For each state `dp[i][j]`, calculate the finish 'distance' after traveling road `i`: `finish_dist = dp[i][j] + dist[i]`.
6. 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`.
7. 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)`
8. After filling the `dp` table, iterate through the number of skips `j` from `0` to `n-1`.
9. For each `j`, calculate the final arrival 'distance' after the last road: `total_dist = dp[n-1][j] + dist[n-1]`.
10. 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.
11. If the loop completes without finding a solution, it's impossible to arrive on time. Return -1.

## Space-Optimized Dynamic Programming
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.
**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.
**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`.
### Explanation
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.

```java
import java.util.Arrays;

class Solution {
    public int minSkips(int[] dist, int speed, int hoursBefore) {
        int n = dist.length;
        // An optional initial check for impossibility.
        long totalDistSum = 0;
        for (int d : dist) {
            totalDistSum += d;
        }
        if ((double) totalDistSum / speed > hoursBefore) {
            return -1;
        }

        long[] dp = new long[n];
        Arrays.fill(dp, Long.MAX_VALUE);
        dp[0] = 0;

        for (int i = 0; i < n - 1; i++) {
            long travelDist = dist[i];
            long[] next_dp = new long[n];
            Arrays.fill(next_dp, Long.MAX_VALUE);

            for (int j = 0; j <= i; j++) {
                if (dp[j] == Long.MAX_VALUE) {
                    continue;
                }

                // Option 1: Don't skip the rest after road i
                long finishDist = dp[j] + travelDist;
                long nextStartNoSkip = (finishDist + speed - 1) / speed * speed;
                next_dp[j] = Math.min(next_dp[j], nextStartNoSkip);

                // Option 2: Skip the rest after road i
                long nextStartSkip = finishDist;
                if (j + 1 < n) {
                    next_dp[j + 1] = Math.min(next_dp[j + 1], nextStartSkip);
                }
            }
            dp = next_dp;
        }

        long maxAllowedDist = (long) hoursBefore * speed;

        for (int j = 0; j < n; j++) {
            if (dp[j] != Long.MAX_VALUE) {
                long totalDist = dp[j] + dist[n - 1];
                if (totalDist <= maxAllowedDist) {
                    return j;
                }
            }
        }

        return -1;
    }
}
```
### Algorithm
1. The core logic is the same as the 2D DP approach, but we optimize space.
2. 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.
3. 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`).
4. Initialize a 1D array `dp` of size `n` with `dp[0] = 0` and others as infinity. This represents the start 'distances' for road 0.
5. Iterate from road `i = 0` to `n-2`. In each iteration, create a `next_dp` array.
6. 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.
7. After the inner loop, replace `dp` with `next_dp` for the next iteration.
8. After iterating through all rests, the final `dp` array will hold the minimum start 'distances' for the last road (`n-1`).
9. 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`.

# Solutions
### Java

```java
class Solution {
public
  int minSkips(int[] dist, int speed, int hoursBefore) {
    int n = dist.length;
    double[][] f = new double[n + 1][n + 1];
    for (int i = 0; i <= n; i++) {
      Arrays.fill(f[i], 1 e20);
    }
    f[0][0] = 0;
    double eps = 1 e - 8;
    for (int i = 1; i <= n; ++i) {
      for (int j = 0; j <= i; ++j) {
        if (j < i) {
          f[i][j] = Math.min(f[i][j], Math.ceil(f[i - 1][j]) +
                                          1.0 * dist[i - 1] / speed - eps);
        }
        if (j > 0) {
          f[i][j] =
              Math.min(f[i][j], f[i - 1][j - 1] + 1.0 * dist[i - 1] / speed);
        }
      }
    }
    for (int j = 0; j <= n; ++j) {
      if (f[n][j] <= hoursBefore + eps) {
        return j;
      }
    }
    return -1;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minSkips(vector<int> &dist, int speed, int hoursBefore) {
    int n = dist.size();
    vector<vector<double>> f(n + 1, vector<double>(n + 1, 1e20));
    f[0][0] = 0;
    double eps = 1e-8;
    for (int i = 1; i <= n; ++i) {
      for (int j = 0; j <= i; ++j) {
        if (j < i) {
          f[i][j] =
              min(f[i][j], ceil(f[i - 1][j] + dist[i - 1] * 1.0 / speed - eps));
        }
        if (j) {
          f[i][j] = min(f[i][j], f[i - 1][j - 1] + dist[i - 1] * 1.0 / speed);
        }
      }
    }
    for (int j = 0; j <= n; ++j) {
      if (f[n][j] <= hoursBefore + eps) {
        return j;
      }
    }
    return -1;
  }
};

```

### Python

```python
class Solution:
    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

```