Minimum skips to arrive at meeting on time
Filed under Amazon
Free read 2 of 3Define dp[i][j] as the minimum time to travel i segments with j skips.
The question
Given an array of road segment times and a speed, find the minimum number of skips required to arrive at a meeting on time, where each skip allows you to ignore the delay of a segment.
Constraints
- 1 <= dist.length <= 1000
- 1 <= speed, hoursBefore <= 10^9
- 0 <= dist[i] <= 10^5
Examples
- Input
- dist = [1,3,2], speed = 4, hoursBefore = 2
- Output
- 1
- Why
- Skipping the second segment allows arrival within the time limit.
Approach
Define dp[i][j] as the minimum time to travel i segments with j skips.
Iterate through segments and skips, updating the DP table based on whether to skip or not.
If the problem is monotonic regarding skips, binary search over the number of skips.
Solution
O(n^2) time, O(n) space
def minSkips(dist, speed, hoursBefore):
n = len(dist)
dp = [float('inf')] * (n + 1)
dp[0] = 0
for d in dist:
new_dp = [float('inf')] * (n + 1)
for j in range(n + 1):
if dp[j] == float('inf'): continue
new_dp[j] = min(new_dp[j], (dp[j] + d + speed - 1) // speed * speed)
if j + 1 <= n: new_dp[j+1] = min(new_dp[j+1], dp[j] + d)
dp = new_dp
for j in range(n + 1):
if dp[j] <= hoursBefore * speed: return j
return -1
Tips
- What they are testing: Test with cases where no skips are possible or all skips are needed.
- Common mistake: Using floating point arithmetic which leads to precision errors; use integer math instead.
Follow-ups
- Optimize from memoization to tabulation
- Provide a binary search approach for a modified version
Related Amazon questions
Collected from public candidate posts and coding forums. Updated Nov 2026.