Skip to content

1883. Minimum Skips to Arrive at Meeting On Time 👍

  • Time: $O(n^2)$
  • Space: $O(n^2)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
 public:
  int minSkips(vector<int>& dist, int speed, int hoursBefore) {
    constexpr double kInf = 1e7;
    constexpr double kEps = 1e-9;
    const int n = dist.size();
    // dp[i][j] := the minimum time, where i is the number of roads we traversed
    // so far and j is the number of skips we did
    vector<vector<double>> dp(n + 1, vector<double>(n + 1, kInf));
    dp[0][0] = 0;

    for (int i = 1; i <= n; ++i) {
      const double d = dist[i - 1];
      dp[i][0] = ceil(dp[i - 1][0] + d / speed - kEps);
      for (int j = 1; j <= i; ++j)
        dp[i][j] = min(dp[i - 1][j - 1] + d / speed,
                       ceil(dp[i - 1][j] + d / speed - kEps));
    }

    for (int j = 0; j <= n; ++j)
      if (dp[n][j] <= hoursBefore)
        return j;

    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
24
25
26
class Solution {
  public int minSkips(int[] dist, int speed, int hoursBefore) {
    final double kInf = 1e7;
    final double kEps = 1e-9;
    final int n = dist.length;
    // dp[i][j] := the minimum time, where i is the number of roads we traversed
    // so far and j is the number of skips we did
    double[][] dp = new double[n + 1][n + 1];
    Arrays.stream(dp).forEach(A -> Arrays.fill(A, kInf));
    dp[0][0] = 0;

    for (int i = 1; i <= n; ++i) {
      final double d = dist[i - 1];
      dp[i][0] = Math.ceil(dp[i - 1][0] + d / speed - kEps);
      for (int j = 1; j <= i; ++j)
        dp[i][j] =
            Math.min(dp[i - 1][j - 1] + d / speed, Math.ceil(dp[i - 1][j] + d / speed - kEps));
    }

    for (int j = 0; j <= n; ++j)
      if (dp[n][j] <= hoursBefore)
        return j;

    return -1;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
  def minSkips(self, dist: list[int], speed: int, hoursBefore: int) -> int:
    kInf = 10**7
    kEps = 1e-9
    n = len(dist)
    # dp[i][j] := the minimum time, where i is the number of roads we traversed
    # so far and j is the number of skips we did
    dp = [[kInf] * (n + 1) for _ in range(n + 1)]
    dp[0][0] = 0

    for i, d in enumerate(dist, 1):
      dp[i][0] = math.ceil(dp[i - 1][0] + d / speed - kEps)
      for j in range(1, i + 1):
        dp[i][j] = min(dp[i - 1][j - 1] + d / speed,
                       math.ceil(dp[i - 1][j] + d / speed - kEps))

    for j, time in enumerate(dp[-1]):
      if time <= hoursBefore:
        return j

    return -1