Minimum Skips to Arrive at Meeting On Time
Description
You have hoursBefore hours to reach a meeting, and the way there is n roads, one after another. dist[i] is the length of road i in kilometres, and you always travel at speed km/h, so road i takes dist[i] / speed hours.
After each road you must rest until the next whole hour before starting the next one. If a road ends at 1.4 hours, you wait until hour 2; if it ends at exactly 2 hours, you do not wait at all. There is no rest after the last road: by then you have arrived.
You may skip some rests. After a skipped rest you start the next road straight away, even at a time that is not a whole hour, so skipping changes when all the later roads end.
Return the fewest rests you must skip to arrive within hoursBefore hours, or -1 if even skipping every rest is too slow.
Examples
Example 1
Input: dist = [2, 1, 3], speed = 3, hoursBefore = 2
Output: 1
Explanation: The roads take 2/3, 1/3 and 1 hour.
- No skips: road 0 ends at 2/3, wait until 1; road 1 ends at 4/3, wait until 2; road 2 ends at 3. Too late.
- Skip only the second rest, the longer wait: road 2 starts at 4/3 and ends at 7/3. Still too late.
- Skip only the first rest: road 1 starts at 2/3 and ends at exactly 1, so the second rest costs nothing, and road 2 ends at 2. On time.
One skip is enough.
Example 2
Input: dist = [4, 4, 4], speed = 5, hoursBefore = 2
Output: -1
Explanation: Driving alone takes 12 / 5 = 2.4 hours, more than 2, so no choice of skips can work.
Example 3
Input: dist = [13, 11, 6], speed = 10, hoursBefore = 3
Output: 2
Explanation: The roads take 1.3, 1.1 and 0.6 hours. With no skips you arrive at 4.6 hours; skipping only the first rest gives 3.6, and only the second gives 3.7. Skipping both, you arrive at exactly 3 hours, just in time.
Constraints
- n == dist.length
- 1 ≤ n ≤ 1000
- 1 ≤ dist[i] ≤ 10^5
- 1 ≤ speed ≤ 10^6
- 1 ≤ hoursBefore ≤ 10^7
Editorial
Brute Force
Intuition
Every rest is a yes-or-no choice. There are n − 1 rests, one after every road but the last, and each one is either kept or skipped. So try both options for each rest, in order, with a recursive function. Standing at the start of road i at time t: drive the road, then either rest until the next whole hour or skip the rest, and ask the same question about the next road. The last road ends the trip, which is then either on time (no more skips needed) or late.
The choices affect each other. It is tempting to skip the rest that wastes the most waiting. That does not work:
In Example 1 the second rest is the longer wait, 2/3 of an hour against 1/3, yet skipping it still arrives late. Skipping the shorter first rest makes road 1 end exactly on the hour, so the second rest costs nothing. What a rest really costs depends on every choice made before it, which is why this approach tries every combination.
Count time in whole units, not decimal hours. Rounding up to the next hour is only exact if the times are exact. In hours, a road time such as 1.3 is a decimal the computer cannot store exactly, and a tiny error just above a whole hour turns into a whole extra hour when it is rounded up. Example 3 shows it: the three road times add up to exactly 3 hours, but the computer's sum is 3.0000000000000004.
So measure time in units of 1/speed of an hour. Then road i takes exactly dist[i] units, one hour is speed units, and "wait for the next whole hour" means "round up to the next multiple of speed", which is (t + speed − 1) // speed * speed. The deadline is hoursBefore × speed units. Every number stays a whole number and every comparison is exact. In C++ and Java that deadline needs a 64-bit integer: it can reach 10^7 × 10^6 = 10^13.
Step-by-Step Explanation
We trace Example 1 in units of 1/3 hour, so the roads take 2, 1 and 3 units and the deadline is 6 units. Each box is one call: which road it starts and at what time t. The call running now is amber, calls waiting for their answers are indigo, and calls whose answer is known are green, showing the fewest skips still needed, or "late".
Step 1: Road 0 from t = 0: it ends at 2. Try resting, then skipping.
Step 2: Road 1 from t = 3 (rest): it ends at 4. Try resting, then skipping.
Step 3: Last road from t = 6: ends at 9, late.
Step 4: Last road from t = 4: ends at 7, late.
Step 5: Back at road 1 from t = 3: resting leads to a late arrival, skipping to a late arrival, so this call answers late.
Step 6: Road 1 from t = 2 (skip): it ends at 3. Try resting, then skipping.
Step 7: Last road from t = 3: ends at 6, on time.
Step 8: Last road from t = 3: ends at 6, on time.
Step 9: Back at road 1 from t = 2: resting leads to 0 more skips, skipping to 1 skip, counting this one, so this call answers 0.
Step 10: Back at road 0 from t = 0: resting leads to a late arrival, skipping to 1 skip, counting this one, so this call answers 1.
Step 11: Return 1: skip the rest after road 0 and keep the one after road 1. All 4 trips were tried.
Brute Force — Rest or Skip, Tried Both Ways — Example 1 in units of 1/3 hour (deadline 6). Each box is one call: which road it starts, and when. Every rest is tried kept and skipped.
Algorithm
- Let
limit = hoursBefore × speed, and letup(t)roundtup to the next multiple ofspeed. fewest(i, t), the fewest skips needed to finish roadsiton − 1on time when roadistarts at timet:- Add
dist[i]tot. - If road
iis the last road, return 0 ift ≤ limit; otherwise the trip is late. - Otherwise return the smaller of
fewest(i + 1, up(t))(rest) and1 + fewest(i + 1, t)(skip).
- Add
- The answer is
fewest(0, 0), or-1if that is late.
Code
#include <algorithm>
#include <climits>
#include <vector>
using namespace std;
class Solution {
const int INF = INT_MAX / 2;
vector<int> dist;
long long speed = 1, limit = 0; // time is counted in units of 1/speed hour, so it stays a whole number
// fewest skips to finish roads i to n - 1 on time, starting road i at time t
int fewest(int i, long long t) {
t += dist[i];
if (i == (int)dist.size() - 1) return t <= limit ? 0 : INF; // no rest after the last road
int rest = fewest(i + 1, (t + speed - 1) / speed * speed); // wait for the next whole hour
int skip = fewest(i + 1, t);
return min(rest, skip == INF ? INF : skip + 1);
}
public:
int minSkips(vector<int>& d, int s, int hoursBefore) {
dist = d;
speed = s;
limit = (long long)hoursBefore * s; // up to 10^13, too big for an int
int best = fewest(0, 0);
return best == INF ? -1 : best;
}
};class Solution:
def minSkips(self, dist: list[int], speed: int, hoursBefore: int) -> int:
n = len(dist)
limit = hoursBefore * speed # time is counted in units of 1/speed hour, so it stays a whole number
INF = float('inf')
def fewest(i: int, t: int) -> float:
# fewest skips to finish roads i to n - 1 on time, starting road i at time t
t += dist[i]
if i == n - 1: # no rest after the last road
return 0 if t <= limit else INF
rest = fewest(i + 1, (t + speed - 1) // speed * speed) # wait for the next whole hour
skip = 1 + fewest(i + 1, t)
return min(rest, skip)
best = fewest(0, 0)
return -1 if best == INF else bestclass Solution {
private static final int INF = Integer.MAX_VALUE / 2;
private int[] dist;
private long speed, limit; // time is counted in units of 1/speed hour, so it stays a whole number
public int minSkips(int[] dist, int speed, int hoursBefore) {
this.dist = dist;
this.speed = speed;
this.limit = (long) hoursBefore * speed; // up to 10^13, too big for an int
int best = fewest(0, 0);
return best == INF ? -1 : best;
}
// fewest skips to finish roads i to n - 1 on time, starting road i at time t
private int fewest(int i, long t) {
t += dist[i];
if (i == dist.length - 1) return t <= limit ? 0 : INF; // no rest after the last road
int rest = fewest(i + 1, (t + speed - 1) / speed * speed); // wait for the next whole hour
int skip = fewest(i + 1, t);
return Math.min(rest, skip == INF ? INF : skip + 1);
}
}Complexity Analysis
Time Complexity: O(2^n). Each of the n − 1 rests doubles the number of paths, so there are 2^(n − 1) complete trips to follow.
Space Complexity: O(n) for the recursion, one call per road.
Why This Approach Is Not Efficient
Every extra road doubles the work. Measured in Python on random roads, 14 roads take 0.001 s, 18 take 0.017 s and 22 take 0.235 s, about four times longer for every two roads added. At that rate 40 roads would take around 17 hours, and the problem allows 1000.
Most of that work is repeated. Two different paths can reach the same road having skipped the same number of rests, and from there on they face exactly the same choices. If one of them gets there earlier, the later one can never do better: starting a road earlier never makes you finish it later, and rounding up to the next hour never turns an earlier time into a later one. So for each road and each number of skips, only the earliest time matters, and there are only about n² such pairs.
Better Approach - Table of Earliest Times
Intuition
Change the question. Instead of following every path, record, for each number of roads done and each number of skips used, the earliest time it can happen. Let dp[i][j] be the earliest time, in units, at which the first i roads are done, each followed by its rest or a skip, having used exactly j skips.
Where each cell comes from. Road i − 1 is followed either by a rest or by a skip:
- rest: start from
dp[i − 1][j], drive the road, and round up:up(dp[i − 1][j] + dist[i − 1]); - skip: start from
dp[i − 1][j − 1], drive the road and carry straight on:dp[i − 1][j − 1] + dist[i − 1]. This is the one extra skip.
dp[i][j] is the smaller of the two. A cell with j > i cannot be reached, since there have only been i rests to skip.
Reading off the answer. The last road has no rest. Once the table is filled, try j = 0, 1, 2, … and return the first j for which dp[n − 1][j] + dist[n − 1] ≤ limit. Trying the fewest skips first is right because skipping one more rest never makes you later, so the first j that fits is the smallest.
Step-by-Step Explanation
We trace Example 1 in units of 1/3 hour. Rows are roads done, columns are j, the skips used. The cell being filled is highlighted and the cells it is built from are marked. The last row adds road 2, which needs no rest, and compares with the deadline of 6 units.
Step 1: Start: dp[0][0] = 0. Nothing else is reachable yet.
Step 2: dp[1][0]: rest after road 0 from 0 gives up(0 + 2) = 3, so 3.
Step 3: dp[1][1]: skipping it from 0 gives 0 + 2 = 2, so 2.
Step 4: dp[2][0]: rest after road 1 from 3 gives up(3 + 1) = 6, so 6.
Step 5: dp[2][1]: rest after road 1 from 2 gives up(2 + 1) = 3; skipping it from 3 gives 3 + 1 = 4, so the smaller, 3.
Step 6: dp[2][2]: skipping it from 2 gives 2 + 1 = 3, so 3.
Step 7: 0 skips: 6 + 3 = 9, more than 6.
Step 8: 1 skip: 3 + 3 = 6, within 6. Answer 1.
Step 9: Return 1.
Table of Earliest Times: Roads Done × Skips Used — Example 1 in units of 1/3 hour. Row = roads done, column j = skips used; each cell is the earliest time, built from the row above.
Algorithm
- Make an n × n table filled with "not reachable" and set
dp[0][0] = 0. - For
ifrom 1 to n − 1, withd = dist[i − 1], and forjfrom 0 toi:rest = up(dp[i − 1][j] + d), ifj < i;skip = dp[i − 1][j − 1] + d, ifj > 0;dp[i][j] = min(rest, skip).
- For
jfrom 0 to n − 1: ifdp[n − 1][j] + dist[n − 1] ≤ limit, returnj. - Return
-1.
Code
#include <algorithm>
#include <climits>
#include <vector>
using namespace std;
class Solution {
public:
int minSkips(vector<int>& dist, int speed, int hoursBefore) {
int n = dist.size();
const long long INF = LLONG_MAX / 4;
// dp[i][j]: earliest time, in units of 1/speed hour, to finish the first i roads and their rests with j skips
vector<vector<long long>> dp(n, vector<long long>(n, INF));
dp[0][0] = 0;
for (int i = 1; i < n; i++) {
long long d = dist[i - 1];
for (int j = 0; j <= i; j++) {
long long rest = j < i ? (dp[i - 1][j] + d + speed - 1) / speed * speed : INF;
long long skip = j > 0 ? dp[i - 1][j - 1] + d : INF;
dp[i][j] = min(rest, skip);
}
}
for (int j = 0; j < n; j++) // fewest skips first
if (dp[n - 1][j] + dist[n - 1] <= (long long)hoursBefore * speed) return j; // the last road needs no rest
return -1;
}
};class Solution:
def minSkips(self, dist: list[int], speed: int, hoursBefore: int) -> int:
n = len(dist)
INF = float('inf')
# dp[i][j]: earliest time, in units of 1/speed hour, to finish the first i roads and their rests with j skips
dp = [[INF] * n for _ in range(n)]
dp[0][0] = 0
for i in range(1, n):
d = dist[i - 1]
for j in range(i + 1):
rest = (dp[i - 1][j] + d + speed - 1) // speed * speed if j < i else INF
skip = dp[i - 1][j - 1] + d if j > 0 else INF
dp[i][j] = min(rest, skip)
for j in range(n): # fewest skips first
if dp[n - 1][j] + dist[n - 1] <= hoursBefore * speed: # the last road needs no rest
return j
return -1import java.util.Arrays;
class Solution {
public int minSkips(int[] dist, int speed, int hoursBefore) {
int n = dist.length;
final long INF = Long.MAX_VALUE / 4;
// dp[i][j]: earliest time, in units of 1/speed hour, to finish the first i roads and their rests with j skips
long[][] dp = new long[n][n];
for (long[] row : dp) Arrays.fill(row, INF);
dp[0][0] = 0;
for (int i = 1; i < n; i++) {
long d = dist[i - 1];
for (int j = 0; j <= i; j++) {
long rest = j < i ? (dp[i - 1][j] + d + speed - 1) / speed * speed : INF;
long skip = j > 0 ? dp[i - 1][j - 1] + d : INF;
dp[i][j] = Math.min(rest, skip);
}
}
for (int j = 0; j < n; j++) // fewest skips first
if (dp[n - 1][j] + dist[n - 1] <= (long) hoursBefore * speed) return j; // the last road needs no rest
return -1;
}
}Complexity Analysis
Time Complexity: O(n²). About n²/2 cells, each worked out in O(1).
Space Complexity: O(n²) for the table.
Why This Approach Is Not Efficient
The time is fine: for 1000 roads the table has about half a million cells, filled in 0.50 s in Python. The waste is memory. The table holds n × n numbers, a million for n = 1000, measured at 24.1 MB in Python. Yet filling row i reads only row i − 1; every row before it is finished with and never read again. A single row is enough, if it is rewritten carefully.
There is also a quick answer the table does not use. Skipping every rest is the fastest possible trip, and it takes exactly sum(dist) units. If that is more than limit, the answer is -1 before anything is filled in.
Optimal Approach - One Row, Filled From Right to Left
Intuition
One row, rewritten for each road. Keep a single row dp[j] for the roads done so far. For the next road, each new dp[j] needs the old dp[j] (for a rest) and the old dp[j − 1] (for a skip). If the row were filled from left to right, dp[j − 1] would already hold the new road's value by the time dp[j] read it, and that road would be counted twice. Filled from right to left, dp[j − 1] still holds the old value when it is read.
![Road 0 of Example 1 applied to a single row two ways. Right to left, dp[1] is built from the old dp[0], 0 + 2 = 2, then dp[0] becomes up(0 + 2) = 3, giving 3 and 2. Left to right, dp[0] becomes 3 first and dp[1] reads it, 3 + 2 = 5, counting road 0 twice, and the answer comes out -1 instead of 1.](https://pub-a1b3030acfb94e84ba8a89fb182c53bc.r2.dev/public/2013/skip_row_v1.webp)
In Example 1, filling left to right would make dp[1] equal 3 + 2 = 5 after road 0 instead of 2, and the final answer would come out -1 instead of 1.
Answer the impossible case at once. If sum(dist) > limit, return -1 straight away. Otherwise skipping every rest is sure to work, so the loop at the end always finds an answer.
Step-by-Step Explanation
We trace Example 1 once more, with a single row indexed by j, the skips used. The cell being written is highlighted and the cells it reads are marked. Watch the order: for each road, j goes down from its largest value to 0.
Step 1: Total distance 6 ≤ 6, so an answer exists. The row starts as [0, ·, ·].
Step 2: Road 0, j = 1: dp[1] = 0 + 2 = 2.
Step 3: Road 0, j = 0: dp[0] = up(0 + 2) = 3.
Step 4: Road 1, j = 2: dp[2] = 2 + 1 = 3.
Step 5: Road 1, j = 1: dp[1] = min(up(2 + 1), 3 + 1) = 3.
Step 6: Road 1, j = 0: dp[0] = up(3 + 1) = 6.
Step 7: Check j = 0: 6 + 3 = 9, more than 6.
Step 8: Check j = 1: 3 + 3 = 6, within 6. Return 1.
Step 9: Return 1.
One Row, Filled From Right to Left — Example 1 in units of 1/3 hour. A single row indexed by j, the skips used, rewritten for each road from the right end to the left.
Algorithm
- Let
limit = hoursBefore × speed. Ifsum(dist) > limit, return-1. - Set
dp = [0, not reachable, …], n cells. - For
ifrom 1 to n − 1, withd = dist[i − 1], and forjfromidown to 0:rest = up(dp[j] + d)ifj < i, andskip = dp[j − 1] + difj > 0;dp[j] = min(rest, skip).
- Return the first
jwithdp[j] + dist[n − 1] ≤ limit.
Right to left, always. It is what lets one row stand in for the whole table.
64-bit numbers. limit can reach 10^13, and the times can pass 2^31 too, so the C++ and Java code keeps them in long long and long.
If you do use hours. A common patch for decimal hours is to subtract a tiny amount, such as 10^-9, before rounding up. On 6,000 random cases at this problem's sizes that patch gave the right answer every time, so it can pass. But the right amount depends on how large the numbers get, and whole units need no guess at all.
Code
#include <algorithm>
#include <climits>
#include <vector>
using namespace std;
class Solution {
public:
int minSkips(vector<int>& dist, int speed, int hoursBefore) {
int n = dist.size();
long long limit = (long long)hoursBefore * speed, total = 0;
for (int d : dist) total += d;
if (total > limit) return -1; // too late even with every rest skipped
const long long INF = LLONG_MAX / 4;
vector<long long> dp(n, INF); // dp[j]: earliest time with j skips, in units of 1/speed hour
dp[0] = 0;
for (int i = 1; i < n; i++) {
long long d = dist[i - 1];
for (int j = i; j >= 0; j--) { // right to left, so dp[j - 1] still holds the previous road's value
long long rest = j < i ? (dp[j] + d + speed - 1) / speed * speed : INF;
long long skip = j > 0 ? dp[j - 1] + d : INF;
dp[j] = min(rest, skip);
}
}
for (int j = 0; j < n; j++)
if (dp[j] + dist[n - 1] <= limit) return j;
return -1;
}
};class Solution:
def minSkips(self, dist: list[int], speed: int, hoursBefore: int) -> int:
n = len(dist)
limit = hoursBefore * speed
if sum(dist) > limit: # too late even with every rest skipped
return -1
INF = float('inf')
dp = [0] + [INF] * (n - 1) # dp[j]: earliest time with j skips, in units of 1/speed hour
for i in range(1, n):
d = dist[i - 1]
for j in range(i, -1, -1): # right to left, so dp[j - 1] still holds the previous road's value
rest = (dp[j] + d + speed - 1) // speed * speed if j < i else INF
skip = dp[j - 1] + d if j > 0 else INF
dp[j] = min(rest, skip)
for j in range(n):
if dp[j] + dist[-1] <= limit:
return j
return -1import java.util.Arrays;
class Solution {
public int minSkips(int[] dist, int speed, int hoursBefore) {
int n = dist.length;
long limit = (long) hoursBefore * speed, total = 0;
for (int d : dist) total += d;
if (total > limit) return -1; // too late even with every rest skipped
final long INF = Long.MAX_VALUE / 4;
long[] dp = new long[n]; // dp[j]: earliest time with j skips, in units of 1/speed hour
Arrays.fill(dp, INF);
dp[0] = 0;
for (int i = 1; i < n; i++) {
long d = dist[i - 1];
for (int j = i; j >= 0; j--) { // right to left, so dp[j - 1] still holds the previous road's value
long rest = j < i ? (dp[j] + d + speed - 1) / speed * speed : INF;
long skip = j > 0 ? dp[j - 1] + d : INF;
dp[j] = Math.min(rest, skip);
}
}
for (int j = 0; j < n; j++)
if (dp[j] + dist[n - 1] <= limit) return j;
return -1;
}
}Complexity Analysis
Time Complexity: O(n²), the same half a million updates as the table, measured at 0.29 s in Python for 1000 roads.
Space Complexity: O(n). One row of n numbers instead of n rows.