Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1883.html
1883. Minimum Skips to Arrive at Meeting On Time
Level
Hard
Description
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 the2
hour mark before traveling the next road. If traveling a road takes exactly2
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 takes0.6
hours. Skipping the rest after the first road will mean you finish traveling the second road right at the2
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^5
1 <= speed <= 10^6
1 <= hoursBefore <= 10^7
Solution
Use dynamic programming. Create a 2D array dp
of n + 1
rows and n + 1
columns, where dp[i][j]
represents the shortest time from dist[0]
to dist[i  1]
with j
skips. Initially, dp[0][0] = 0
. For the other cases, dp[i][j]
is the minimum of ((dp[i  1][j] + dist[i  1]  1) / speed + 1) * speed
and dp[i  1][j  1] + dist[i  1]
. Finally, return the smallest j
such that dp[n][j] <= hoursBefore * speed
.
Note that all values in dp
have been multiplied by speed
to avoid floatingpoint errors.

class Solution { public int minSkips(int[] dist, int speed, int hoursBefore) { int length = dist.length; long[][] dp = new long[length + 1][length + 1]; for (int i = 0; i <= length; i++) Arrays.fill(dp[i], Long.MAX_VALUE / 2); dp[0][0] = 0; for (int i = 0; i <= length; i++) { for (int j = 0; j <= i; j++) { if (j != i) dp[i][j] = Math.min(dp[i][j], ((dp[i  1][j] + dist[i  1]  1) / speed + 1) * speed); if (j != 0) dp[i][j] = Math.min(dp[i][j], dp[i  1][j  1] + dist[i  1]); } } for (int j = 0; j <= length; j++) { if (dp[length][j] <= (long) hoursBefore * speed) return j; } return 1; } } ############ class Solution { public int minSkips(int[] dist, int speed, int hoursBefore) { int n = dist.length; int[][] dp = new int[n + 1][n + 1]; for (int i = 0; i <= n; ++i) { for (int j = 0; j <= n; ++j) { dp[i][j] = Integer.MAX_VALUE; } } dp[0][0] = 0; for (int i = 1; i <= n; ++i) { for (int j = 0; j <= i; ++j) { if (i != j) { dp[i][j] = Math.min( dp[i][j], ((dp[i  1][j] + dist[i  1]  1) / speed + 1) * speed); } if (j > 0) { dp[i][j] = Math.min(dp[i][j], dp[i  1][j  1] + dist[i  1]); } } } for (int i = 0; i <= n; ++i) { if (dp[n][i] <= hoursBefore * speed) { return i; } } return 1; } }

// OJ: https://leetcode.com/problems/minimumskipstoarriveatmeetingontime/ // Time: O(N^2) // Space: O(N^2) class Solution { public: int minSkips(vector<int>& D, int S, int H) { long N = D.size(), mx = (long)S * H, dp[1001][1001] = {}; memset(dp, 0x3f, sizeof(dp)); for (int i = 0; i <= N; ++i) dp[0][i] = 0; for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { dp[i + 1][j] = min(j  1 >= 0 ? dp[i][j  1] + D[i] : INT_MAX, ((long)dp[i][j] + D[i] + S  1) / S * S); if (i == N  1 && dp[i + 1][j] <= mx) return j; } } return 1; } };

class Solution: def minSkips(self, dist: List[int], speed: int, hoursBefore: int) > int: n = len(dist) dp = [[inf] * (n + 1) for _ in range(n + 1)] dp[0][0] = 0 for i in range(1, n + 1): for j in range(i + 1): if i != j: dp[i][j] = min( dp[i][j], ((dp[i  1][j] + dist[i  1]  1) // speed + 1) * speed, ) if j > 0: dp[i][j] = min(dp[i][j], dp[i  1][j  1] + dist[i  1]) for i in range(n + 1): if dp[n][i] <= hoursBefore * speed: return i return 1

func minSkips(dist []int, speed int, hoursBefore int) int { n := len(dist) f := make([][]float64, n+1) for i := range f { f[i] = make([]float64, n+1) for j := range f[i] { f[i][j] = 1e20 } } f[0][0] = 0 eps := 1e8 for i := 1; i <= n; i++ { for j := 0; j <= i; j++ { if j < i { f[i][j] = math.Min(f[i][j], math.Ceil(f[i1][j]+float64(dist[i1])/float64(speed)eps)) } if j > 0 { f[i][j] = math.Min(f[i][j], f[i1][j1]+float64(dist[i1])/float64(speed)) } } } for j := 0; j <= n; j++ { if f[n][j] <= float64(hoursBefore) { return j } } return 1 }

function minSkips(dist: number[], speed: number, hoursBefore: number): number { const n = dist.length; const f = Array.from({ length: n + 1 }, () => Array.from({ length: n + 1 }, () => Infinity)); f[0][0] = 0; const eps = 1e8; for (let i = 1; i <= n; ++i) { for (let j = 0; j <= i; ++j) { if (j < i) { f[i][j] = Math.min(f[i][j], Math.ceil(f[i  1][j] + dist[i  1] / speed  eps)); } if (j) { f[i][j] = Math.min(f[i][j], f[i  1][j  1] + dist[i  1] / speed); } } } for (let j = 0; j <= n; ++j) { if (f[n][j] <= hoursBefore + eps) { return j; } } return 1; }