365. Minimum Van Speed
A delivery van must drive through n legs in a fixed order, and dist[i] is the length in kilometres of the i-th leg. Every leg except the last one can only be started on a whole hour, so after finishing a leg the driver waits until the next whole hour if needed. The last leg ends the trip as soon as it is driven.
The van travels at one constant integer speed in km/h. Return the smallest positive integer speed that lets the whole trip finish within hour hours, or -1 if no speed does. The number hour has at most two digits after the decimal point, and the answer never exceeds 10^7 when it exists.
Example 1
- Input:
- dist = [4,2,5], hour = 4.5
- Output:
- 4
- Explanation:
At speed 4 the first two legs take 1 hour each (waiting included) and the last takes 1.25 hours, so 3.25 hours, which fits. At speed 3 the trip needs 2 + 1 + 5/3, about 4.67 hours, which is too long. The answer is 4.
Example 2
- Input:
- dist = [4,2,5], hour = 1.5
- Output:
- -1
- Explanation:
The first two legs need at least one whole hour each, so the trip takes more than 2 hours at any speed. That does not fit in 1.5 hours, so the answer is -1.
Constraints
1 ≤ dist.length ≤ 105
1 ≤ dist[i] ≤ 105
1 ≤ hour ≤ 106, with at most two digits after the decimal point.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(n log M), where M = 10^7
- Space
- O(1)