Welcome to Subscribe On Youtube
1870. Minimum Speed to Arrive on Time
Description
You are given a floating-point number hour, representing the amount of time you have to reach the office. To commute to the office, you must take n trains in sequential order. You are also given an integer array dist of length n, where dist[i] describes the distance (in kilometers) of the ith train ride.
Each train can only depart at an integer hour, so you may need to wait in between each train ride.
- For example, if the
1sttrain ride takes1.5hours, you must wait for an additional0.5hours before you can depart on the2ndtrain ride at the 2 hour mark.
Return the minimum positive integer speed (in kilometers per hour) that all the trains must travel at for you to reach the office on time, or -1 if it is impossible to be on time.
Tests are generated such that the answer will not exceed 107 and hour will have at most two digits after the decimal point.
Example 1:
Input: dist = [1,3,2], hour = 6 Output: 1 Explanation: At speed 1: - The first train ride takes 1/1 = 1 hour. - Since we are already at an integer hour, we depart immediately at the 1 hour mark. The second train takes 3/1 = 3 hours. - Since we are already at an integer hour, we depart immediately at the 4 hour mark. The third train takes 2/1 = 2 hours. - You will arrive at exactly the 6 hour mark.
Example 2:
Input: dist = [1,3,2], hour = 2.7 Output: 3 Explanation: At speed 3: - The first train ride takes 1/3 = 0.33333 hours. - Since we are not at an integer hour, we wait until the 1 hour mark to depart. The second train ride takes 3/3 = 1 hour. - Since we are already at an integer hour, we depart immediately at the 2 hour mark. The third train takes 2/3 = 0.66667 hours. - You will arrive at the 2.66667 hour mark.
Example 3:
Input: dist = [1,3,2], hour = 1.9 Output: -1 Explanation: It is impossible because the earliest the third train can depart is at the 2 hour mark.
Constraints:
n == dist.length1 <= n <= 1051 <= dist[i] <= 1051 <= hour <= 109- There will be at most two digits after the decimal point in
hour.
Solutions
Binary search.
Template 1:
boolean check(int x) {
}
int search(int left, int right) {
while (left < right) {
int mid = (left + right) >> 1;
if (check(mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
Template 2:
boolean check(int x) {
}
int search(int left, int right) {
while (left < right) {
int mid = (left + right + 1) >> 1;
if (check(mid)) {
left = mid;
} else {
right = mid - 1;
}
}
return left;
}
When doing binary search problems, you can follow the following routine:
- Write out the loop condition $left < right$;
- Inside the loop, you might as well write $mid = \lfloor \frac{left + right}{2} \rfloor$ first;
- According to the specific problem, implement the $check()$ function (sometimes the logic is very simple, you can not define $check$), think about whether to use $right = mid$ (Template $1$) or $left = mid$ (Template $2$);
- If $right = mid$, then write the else statement $left = mid + 1$, and there is no need to change the calculation of $mid$, that is, keep $mid = \lfloor \frac{left + right}{2} \rfloor$;
- If $left = mid$, then write the else statement $right = mid - 1$, and add +1 when calculating $mid$, that is, $mid = \lfloor \frac{left + right + 1}{2} \rfloor$;
- When the loop ends, $left$ equals $right$.
Note that the advantage of these two templates is that they always keep the answer within the binary search interval, and the value corresponding to the end condition of the binary search is exactly at the position of the answer. For the case that may have no solution, just check whether the $left$ or $right$ after the binary search ends satisfies the problem.
-
class Solution { public: int minSpeedOnTime(vector<int>& dist, double hour) { int left = 1, right = 1e7; while (left < right) { int mid = (left + right) >> 1; if (check(dist, mid, hour)) { right = mid; } else { left = mid + 1; } } return check(dist, left, hour) ? left : -1; } bool check(vector<int>& dist, int speed, double hour) { double res = 0; for (int i = 0; i < dist.size(); ++i) { double cost = dist[i] * 1.0 / speed; res += (i == dist.size() - 1 ? cost : ceil(cost)); } return res <= hour; } }; -
class Solution: def minSpeedOnTime(self, dist: List[int], hour: float) -> int: def check(speed): res = 0 for i, d in enumerate(dist): res += (d / speed) if i == len(dist) - 1 else math.ceil(d / speed) return res <= hour r = 10**7 + 1 ans = bisect_left(range(1, r), True, key=check) + 1 return -1 if ans == r else ans -
func minSpeedOnTime(dist []int, hour float64) int { n := len(dist) const mx int = 1e7 x := sort.Search(mx, func(s int) bool { s++ var cost float64 for _, v := range dist[:n-1] { cost += math.Ceil(float64(v) / float64(s)) } cost += float64(dist[n-1]) / float64(s) return cost <= hour }) if x == mx { return -1 } return x + 1 } -
/** * @param {number[]} dist * @param {number} hour * @return {number} */ var minSpeedOnTime = function (dist, hour) { if (dist.length > Math.ceil(hour)) return -1; let left = 1, right = 10 ** 7; while (left < right) { let mid = (left + right) >> 1; if (arriveOnTime(dist, mid, hour)) { right = mid; } else { left = mid + 1; } } return left; }; function arriveOnTime(dist, speed, hour) { let res = 0.0; let n = dist.length; for (let i = 0; i < n; i++) { let cost = parseFloat(dist[i]) / speed; if (i != n - 1) { cost = Math.ceil(cost); } res += cost; } return res <= hour; } -
impl Solution { pub fn min_speed_on_time(dist: Vec<i32>, hour: f64) -> i32 { let n = dist.len(); let check = |speed| { let mut cur = 0.0; for (i, &d) in dist.iter().enumerate() { if i == n - 1 { cur += (d as f64) / (speed as f64); } else { cur += ((d as f64) / (speed as f64)).ceil(); } } cur <= hour }; let mut left = 1; let mut right = 1e7 as i32; while left < right { let mid = left + (right - left) / 2; if !check(mid) { left = mid + 1; } else { right = mid; } } if check(left) { return left; } -1 } } -
function minSpeedOnTime(dist: number[], hour: number): number { if (dist.length > Math.ceil(hour)) { return -1; } const n = dist.length; const m = 10 ** 7; const check = (v: number): boolean => { let s = 0; for (let i = 0; i < n; ++i) { const t = dist[i] / v; s += i === n - 1 ? t : Math.ceil(t); } return s <= hour; }; let [l, r] = [1, m + 1]; while (l < r) { const mid = (l + r) >> 1; if (check(mid)) { r = mid; } else { l = mid + 1; } } return l > m ? -1 : l; }