Minimum Skips to Arrive at Meeting On Time — Solution
Minimum Skips to Arrive at Meeting On Time solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Minimum Skips to Arrive at Meeting On Time is a hard coding problem on arrays and dynamic programming, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Arrays, Dynamic Programming
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You have hoursBefore hours to reach a meeting, and the way there is n roads driven in order; road i is dist[i] kilometres long. You always drive at speed km/h.
After each road you must rest until the next whole hour before starting the next road. For example, if a road ends 1.4 hours after you set off, you wait until hour 2; if it ends exactly at hour 2, there is no wait. No rest is needed after the last road, since you have arrived.
To save time you may skip some rests and start the next road immediately. Return the minimum number of skips needed to arrive at the meeting on time (arriving exactly at hour hoursBefore counts), or -1 if that is impossible.
Example 1
Input: dist = [3,1,2], speed = 4, hoursBefore = 2
Output: 1
Explanation: Without skips you arrive at 2.5 hours. Skip the first rest: 0.75 + 0.25 = 1.0 hours, no wait, then 1.0 + 0.5 = 1.5 hours.
Example 2
Input: dist = [2,3,1], speed = 3, hoursBefore = 2
Output: 2
Explanation: The roads need exactly 2 hours of driving, so no waiting at all is affordable.
Example 3
Input: dist = [5,5], speed = 2, hoursBefore = 4
Output: -1
Explanation: Driving alone takes 5 hours.
Constraints
n == dist.length1 <= n <= 10001 <= dist[i] <= 10^51 <= speed <= 10^61 <= hoursBefore <= 10^7
Hints for Minimum Skips to Arrive at Meeting On Time
Hint 1
Greedy choices of which rests to skip go wrong; think about the best arrival time after
iroads having used exactlyjskips.Hint 2
Fractions of hours invite floating-point errors. Measure time in units of
1 / speedhours instead: roadithen takes exactlydist[i]units, and 'the next whole hour' is the next multiple ofspeed.Hint 3
dp[j]= the earliest time (in those units) after the current road withjskips. Resting roundst + dist[i]up to a multiple ofspeed; skipping keepst + dist[i]and uses one more skip. Answer: the smallestjwithdp[j] + dist[n-1] <= hoursBefore · speed.
How to solve Minimum Skips to Arrive at Meeting On Time
With a fixed number of skips, finishing a prefix of roads earlier is never worse, so dp[i][j] = the earliest finishing time of the first i roads with j skips is an optimal-substructure state. Scaling time by speed turns every quantity into an integer and the rest rule into 'round up to a multiple of speed'.
Approach
- Work in units of
1 / speedhours: roaditakesdist[i]units and the deadline ishoursBefore · speedunits (use 64-bit integers). dp[0] = 0, all other entries infinite.- For every road
iexcept the last, buildnext: from each finitedp[j], lett = dp[j] + dist[i]; resting givesnext[j] = min(next[j], ceil(t / speed) · speed); skipping givesnext[j+1] = min(next[j+1], t). - Finally, return the smallest
jwithdp[j] + dist[n-1] <= hoursBefore · speed, or-1if there is none.
Why it works
Among plans that cover the first i roads with exactly j skips, the one that finishes earliest dominates: rounding up to the next hour is monotone, so starting the remaining roads earlier can only make every later time earlier or equal. So keeping the minimum per (i, j) loses nothing, and the two transitions cover the only decision after each road. Integer units make the rounding exact — no floating-point comparison can misjudge a time that lands exactly on an hour.
Complexity
- Time —
O(n^2) - Space —
O(n)
Pitfalls
- Floating-point times such as 1/3 + 2/3 can come out as 0.999… or 1.000…1 and wrongly add or skip an hour of waiting — use integer units.
- No rest after the last road: add the final road without rounding.
hoursBefore · speedcan reach 10^13 — compute it in 64 bits.
Reference solution
Python
from typing import List
def minSkips(dist: List[int], speed: int, hoursBefore: int) -> int:
n = len(dist)
INF = float('inf')
dp = [INF] * (n + 1)
dp[0] = 0
for i in range(n - 1):
nd = [INF] * (n + 1)
for j in range(i + 1):
if dp[j] == INF:
continue
t = dp[j] + dist[i]
rested = (t + speed - 1) // speed * speed
if rested < nd[j]:
nd[j] = rested
if t < nd[j + 1]:
nd[j + 1] = t
dp = nd
limit = hoursBefore * speed
for j in range(n):
if dp[j] != INF and dp[j] + dist[n - 1] <= limit:
return j
return -1Java
public static int minSkips(int[] dist, int speed, int hoursBefore) {
int n = dist.length;
final long INF = Long.MAX_VALUE / 4;
long[] dp = new long[n + 1];
Arrays.fill(dp, INF);
dp[0] = 0;
for (int i = 0; i < n - 1; i++) {
long[] nd = new long[n + 1];
Arrays.fill(nd, INF);
for (int j = 0; j <= i; j++) {
if (dp[j] == INF) continue;
long t = dp[j] + dist[i];
long rested = (t + speed - 1) / speed * speed;
if (rested < nd[j]) nd[j] = rested;
if (t < nd[j + 1]) nd[j + 1] = t;
}
dp = nd;
}
long limit = (long) hoursBefore * speed;
for (int j = 0; j < n; j++) {
if (dp[j] != INF && dp[j] + dist[n - 1] <= limit) return j;
}
return -1;
}C++
int minSkips(vector<int>& dist, int speed, int hoursBefore) {
int n = dist.size();
const long long INF = LLONG_MAX / 4;
vector<long long> dp(n + 1, INF);
dp[0] = 0;
for (int i = 0; i < n - 1; i++) {
vector<long long> nd(n + 1, INF);
for (int j = 0; j <= i; j++) {
if (dp[j] == INF) continue;
long long t = dp[j] + dist[i];
long long rested = (t + speed - 1) / speed * speed;
nd[j] = min(nd[j], rested);
nd[j + 1] = min(nd[j + 1], t);
}
dp = nd;
}
long long limit = (long long)hoursBefore * speed;
for (int j = 0; j < n; j++) {
if (dp[j] != INF && dp[j] + dist[n - 1] <= limit) return j;
}
return -1;
}JavaScript
var minSkips = function(dist, speed, hoursBefore) {
var n = dist.length, INF = Infinity;
var dp = new Array(n + 1).fill(INF);
dp[0] = 0;
for (var i = 0; i < n - 1; i++) {
var nd = new Array(n + 1).fill(INF);
for (var j = 0; j <= i; j++) {
if (dp[j] === INF) continue;
var t = dp[j] + dist[i];
var rested = Math.floor((t + speed - 1) / speed) * speed;
if (rested < nd[j]) nd[j] = rested;
if (t < nd[j + 1]) nd[j + 1] = t;
}
dp = nd;
}
var limit = hoursBefore * speed;
for (var j = 0; j < n; j++) {
if (dp[j] !== INF && dp[j] + dist[n - 1] <= limit) return j;
}
return -1;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming