Minimum Integer Speed to Cross All Segments Before a Deadline
Solve this Problemdist[i] distance units each, traveled in order at a single constant integer speed. Every segment except the last one may only be started at the top of an hour (so even finishing a segment slightly early still means waiting until the next full hour to begin the next one); the final segment has no such restriction and can end at any exact moment. Given a deadline in minutes, deadlineMinutes, find the minimum integer speed that completes the whole route in time, or -1 if no integer speed manages it.
Every non-final segment effectively costs ⌈dist[i] / speed⌉ whole hours because of the hour-boundary rule, while the final segment costs exactly dist[last] / speed hours — computed here through cross-multiplication rather than division, so every comparison stays in exact integers with no fractional or floating-point arithmetic at all.
Total travel time only ever decreases (or stays flat) as speed increases, which makes this a binary search on the answerBinary Search on the AnswerInstead of searching a sorted array, the search runs directly over the space of possible answers (here, every candidate integer speed). It works whenever "is this candidate good enough?" is monotonic — once a candidate works, every faster candidate keeps working too. — search directly over candidate speeds rather than trying to reason about the schedule algebraically.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ number of segments ≤ 100 - ◆
1 ≤ dist[i] ≤ 1000 - ◆
1 ≤ deadlineMinutes ≤ 10⁴
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Try Every Integer Speed From 1 Upward
BruteEvery segment except the last can only be started at the top of an hour, so each of those segments effectively costs ⌈dist[i] / speed⌉ full hours — even a tiny overrun rounds up to a whole extra hour. The final segment has no such restriction, so it only costs dist[last] / speed hours exactly, computed without rounding via cross-multiplication (to avoid any fractional arithmetic). Try speed = 1, 2, 3, ... and check whether the total time fits the deadline; the first speed that works is the answer, since a faster speed can only ever finish sooner or at the same time. Correct, but checking every candidate speed one at a time is wasteful once distances get large.
O(n · maxSpeed)O(1)1class Solution {
2 public int minSpeedToArrive(int[] dist, int deadlineMinutes) {
3 int n = dist.length;
4 if ((long) (n - 1) * 60 > deadlineMinutes) return -1;
5 int maxDist = 0;
6 for (int d : dist) maxDist = Math.max(maxDist, d);
7 for (int speed = 1; speed <= 60 * maxDist; speed++) {
8 if (feasible(dist, deadlineMinutes, speed)) return speed;
9 }
10 return -1;
11 }
12
13 private boolean feasible(int[] dist, int deadlineMinutes, int speed) {
14 int n = dist.length;
15 long wholeMin = 0;
16 for (int i = 0; i < n - 1; i++) {
17 wholeMin += 60L * ((dist[i] + speed - 1) / speed);
18 }
19 if (wholeMin > deadlineMinutes) return false;
20 long remaining = deadlineMinutes - wholeMin;
21 return (long) dist[n - 1] * 60 <= remaining * (long) speed;
22 }
23}Optimal — Binary Search on the Speed
OptimalTotal travel time only ever goes down (or stays the same) as speed increases — a faster speed can never take longer. That monotonic relationship is exactly what binary search needs: search the candidate speeds from 1 up to a safely large bound (60 times the longest segment is always enough, since every segment finishes within a single hour at that speed), and whenever a candidate speed meets the deadline, remember it and try a slower speed; otherwise it's too slow, so search faster.
O(n · log(maxSpeed))O(1)1class Solution {
2 public int minSpeedToArrive(int[] dist, int deadlineMinutes) {
3 int n = dist.length;
4 if ((long) (n - 1) * 60 > deadlineMinutes) return -1;
5 int maxDist = 0;
6 for (int d : dist) maxDist = Math.max(maxDist, d);
7 int lo = 1, hi = 60 * maxDist, ans = -1;
8 while (lo <= hi) {
9 int mid = lo + (hi - lo) / 2;
10 if (feasible(dist, deadlineMinutes, mid)) {
11 ans = mid;
12 hi = mid - 1;
13 } else {
14 lo = mid + 1;
15 }
16 }
17 return ans;
18 }
19
20 private boolean feasible(int[] dist, int deadlineMinutes, int speed) {
21 int n = dist.length;
22 long wholeMin = 0;
23 for (int i = 0; i < n - 1; i++) {
24 wholeMin += 60L * ((dist[i] + speed - 1) / speed);
25 }
26 if (wholeMin > deadlineMinutes) return false;
27 long remaining = deadlineMinutes - wholeMin;
28 return (long) dist[n - 1] * 60 <= remaining * (long) speed;
29 }
30}