You are given an array dist of positive integers where dist[i] represents the distance of the i-th road segment you must travel, and an integer speed representing your constant travel speed. You must arrive at a meeting within hoursBefore hours (a floating-point number).
After each segment (except the last), you may choose to skip waiting for the next integer hour (i.e., you do not round up your travel time to the next integer hour). If you do not skip, you must wait until the next integer hour to start the next segment.
Your goal is to determine the minimum number of skips required to arrive on time. If it is not possible, return -1.
At first glance, this problem appears similar to finding the minimum number of modifications needed to fit within a time constraint. A brute-force approach would be to try all possible combinations of skips, but with up to 1000 segments, this is computationally infeasible.
The key realization is that after each segment (except the last), you can either round up your current time to the next integer (wait for the next hour) or skip the wait. Skipping is valuable but limited, so we want to use skips only when necessary.
This suggests a dynamic programming approach: for each segment and for each possible number of skips used, track the minimum possible total travel time. We optimize by always making the best choice at each step, given the skips used so far.
We use dynamic programming to solve this problem efficiently:
dp[i][k] be the minimum time (in fractional hours) to finish the first i segments using exactly k skips.dp[0][0] = 0 (no distance covered, no skips used).i and each possible skip count k:
k such that dp[n][k] ≤ hoursBefore.speed.
Input: dist = [1,3,2], speed = 4, hoursBefore = 2.7
O(2^n), which is impractical for large n.
n segments and at most n skips, so O(n^2) states. Each state is updated in O(1) time. O(n^2) time and O(n^2) space.
The Minimum Skips to Arrive at Meeting On Time problem is a classic example of optimizing resource usage (skips) under constraints (time). By modeling the problem with dynamic programming, we efficiently explore all possible skip usages, ensuring we find the minimum necessary to arrive on time. The solution is elegant, leveraging state transitions and careful rounding to minimize unnecessary waiting.
import math
class Solution:
def minSkips(self, dist, speed, hoursBefore):
n = len(dist)
INF = float('inf')
# dp[i][k]: min time (in units of speed) to reach i-th segment with k skips
dp = [ [INF] * (n+1) for _ in range(n+1) ]
dp[0][0] = 0
for i in range(1, n+1):
d = dist[i-1]
for k in range(0, i+1):
# If no skip after segment i-1
if k <= i-1:
prev = dp[i-1][k]
if i == n:
# Last segment, no rounding
time = prev + d
else:
# Round up to next integer
time = ((prev + d + speed - 1) // speed) * speed
dp[i][k] = min(dp[i][k], time)
# If skip after segment i-1
if k > 0:
prev = dp[i-1][k-1]
time = prev + d
dp[i][k] = min(dp[i][k], time)
for k in range(n+1):
if dp[n][k] <= hoursBefore * speed + 1e-8:
return k
return -1
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
class Solution {
public:
int minSkips(vector<int>& dist, int speed, double hoursBefore) {
int n = dist.size();
const long long INF = 1e18;
vector<vector<long long>> dp(n+1, vector<long long>(n+1, INF));
dp[0][0] = 0;
for (int i = 1; i <= n; ++i) {
int d = dist[i-1];
for (int k = 0; k <= i; ++k) {
// No skip
if (k <= i-1) {
long long prev = dp[i-1][k];
long long time;
if (i == n) {
time = prev + d;
} else {
time = ((prev + d + speed - 1) / speed) * speed;
}
dp[i][k] = min(dp[i][k], time);
}
// Skip
if (k > 0) {
long long prev = dp[i-1][k-1];
long long time = prev + d;
dp[i][k] = min(dp[i][k], time);
}
}
}
for (int k = 0; k <= n; ++k) {
if (dp[n][k] <= hoursBefore * speed + 1e-8)
return k;
}
return -1;
}
};
class Solution {
public int minSkips(int[] dist, int speed, double hoursBefore) {
int n = dist.length;
long INF = (long)1e18;
long[][] dp = new long[n+1][n+1];
for (int i = 0; i <= n; ++i)
for (int j = 0; j <= n; ++j)
dp[i][j] = INF;
dp[0][0] = 0;
for (int i = 1; i <= n; ++i) {
int d = dist[i-1];
for (int k = 0; k <= i; ++k) {
// No skip
if (k <= i-1) {
long prev = dp[i-1][k];
long time;
if (i == n) {
time = prev + d;
} else {
time = ((prev + d + speed - 1) / speed) * speed;
}
dp[i][k] = Math.min(dp[i][k], time);
}
// Skip
if (k > 0) {
long prev = dp[i-1][k-1];
long time = prev + d;
dp[i][k] = Math.min(dp[i][k], time);
}
}
}
for (int k = 0; k <= n; ++k) {
if (dp[n][k] <= hoursBefore * speed + 1e-8)
return k;
}
return -1;
}
}
var minSkips = function(dist, speed, hoursBefore) {
const n = dist.length;
const INF = 1e18;
let dp = Array.from({length: n+1}, () => Array(n+1).fill(INF));
dp[0][0] = 0;
for (let i = 1; i <= n; ++i) {
let d = dist[i-1];
for (let k = 0; k <= i; ++k) {
// No skip
if (k <= i-1) {
let prev = dp[i-1][k];
let time;
if (i === n) {
time = prev + d;
} else {
time = Math.ceil((prev + d) / speed) * speed;
}
dp[i][k] = Math.min(dp[i][k], time);
}
// Skip
if (k > 0) {
let prev = dp[i-1][k-1];
let time = prev + d;
dp[i][k] = Math.min(dp[i][k], time);
}
}
}
for (let k = 0; k <= n; ++k) {
if (dp[n][k] <= hoursBefore * speed + 1e-8)
return k;
}
return -1;
};