Minimum Speed to Arrive on Time
Problem
Given dist[] of leg lengths and a deadline `hour`, return the minimum integer speed that lets you finish in time. Every leg except the last must round up its travel time.
dist = [1,3,2], hour = 61def min_speed_on_time(dist, hour):
n = len(dist)
if hour <= n - 1: return -1
def ok(v):
t = 0.0
for i in range(n - 1):
t += -(-dist[i] // v) # ceil
t += dist[-1] / v
return t <= hour
lo, hi = 1, 10**7
if not ok(hi): return -1
while lo < hi:
mid = (lo + hi) // 2
if ok(mid): hi = mid
else: lo = mid + 1
return lofunction minSpeedOnTime(dist, hour) {
const n = dist.length;
if (hour <= n - 1) return -1;
function ok(v) {
let t = 0;
for (let i = 0; i < n - 1; i++) t += Math.ceil(dist[i] / v);
t += dist[n - 1] / v;
return t <= hour;
}
let lo = 1, hi = 1e7;
if (!ok(hi)) return -1;
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
if (ok(mid)) hi = mid; else lo = mid + 1;
}
return lo;
}class Solution {
public int minSpeedOnTime(int[] dist, double hour) {
int n = dist.length;
if (hour <= n - 1) return -1;
int lo = 1, hi = 10000000;
while (lo < hi) {
int mid = (lo + hi) >>> 1;
double t = 0;
for (int i = 0; i < n - 1; i++) t += (dist[i] + mid - 1) / mid;
t += (double) dist[n - 1] / mid;
if (t <= hour) hi = mid; else lo = mid + 1;
}
double t = 0;
for (int i = 0; i < n - 1; i++) t += (dist[i] + lo - 1) / lo;
t += (double) dist[n - 1] / lo;
return t <= hour ? lo : -1;
}
}int minSpeedOnTime(vector<int>& dist, double hour) {
int n = dist.size();
if (hour <= n - 1) return -1;
int lo = 1, hi = 10000000;
while (lo < hi) {
int mid = (lo + hi) / 2;
double t = 0;
for (int i = 0; i < n - 1; i++) t += (dist[i] + mid - 1) / mid;
t += (double) dist[n - 1] / mid;
if (t <= hour) hi = mid; else lo = mid + 1;
}
double t = 0;
for (int i = 0; i < n - 1; i++) t += (dist[i] + lo - 1) / lo;
t += (double) dist[n - 1] / lo;
return t <= hour ? lo : -1;
}Explanation
Going faster never makes you later, so "does speed v finish on time?" is monotone in v. That lets us binary-search the speed and find the smallest one that meets the deadline.
The check ok(v) adds up travel time. Every leg except the last must wait for the next whole hour to start, so its time is rounded up: ceil(dist[i] / v). The final leg is not rounded, so it contributes the exact fraction dist[last] / v. If the total is <= hour, the speed works.
If ok(mid) is true we try slower (hi = mid); otherwise we go faster (lo = mid + 1). There is also an early impossibility check: if even the largest speed cannot make it (or hour <= n - 1, since each rounded leg costs at least 1 hour), we return -1.
Example: dist = [1,3,2], hour = 6. At speed 1: ceil(1) + ceil(3) + 2/1 = 1 + 3 + 2 = 6, exactly on time, and no slower speed exists. So the answer is 1.
The rounding-up of all-but-last legs is the key detail that makes the time function correct.