Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1870.html
1870. Minimum Speed to Arrive on Time
Level
Medium
Description
You are given a floatingpoint 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
1st
train ride takes1.5
hours, you must wait for an additional0.5
hours before you can depart on the2nd
train 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 10^7
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.length
1 <= n <= 10^5
1 <= dist[i] <= 10^5
1 <= hour <= 10^9
 There will be at most two digits after the decimal point in
hour
.
Solution
The maximum possible speed is 10^7
. If it is still impossible to arrive on time using the maximum possible speed, return 1. Then let high = 10000000
and low = 1
, and use binary search to find the minimum speed to arrive on time.

class Solution { public int minSpeedOnTime(int[] dist, double hour) { int high = 10000000; if (!canArrive(dist, hour, high)) return 1; int low = 1; while (low < high) { int mid = (high  low) / 2 + low; if (canArrive(dist, hour, mid)) high = mid; else low = mid + 1; } return low; } public boolean canArrive(int[] dist, double hour, int speed) { double total = 0; int length = dist.length; for (int i = 0; i < length; i++) { if (i == length  1) total += 1.0 * dist[i] / speed; else { int curr = dist[i] / speed; if (dist[i] % speed != 0) curr++; total += curr; } } return total <= hour; } } ############ class Solution { public int minSpeedOnTime(int[] dist, double hour) { int left = 1, right = (int) 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; } private boolean check(int[] dist, int speed, double hour) { double res = 0; for (int i = 0; i < dist.length; ++i) { double cost = dist[i] * 1.0 / speed; res += (i == dist.length  1 ? cost : Math.ceil(cost)); } return res <= hour; } }

// OJ: https://leetcode.com/problems/minimumspeedtoarriveontime/ // Time: O(NlogT) where T is the maximum possible speed // Space: O(1) class Solution { bool valid(vector<int>& A, int speed, double hour) { double time = 0; for (int i = 0; i < A.size(); ++i) { time = ceil(time); time += (double)A[i] / speed; if (time > hour) return false; } return true; } public: int minSpeedOnTime(vector<int>& A, double hour) { if (hour < A.size()  1) return 1; long L = 1, R = 1e7; while (L <= R) { long M = (L + R) / 2; if (valid(A, M, hour)) R = M  1; else L = M + 1; } return L > 1e7 ? 1 : L; } };

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 ############ # 1870. Minimum Speed to Arrive on Time # https://leetcode.com/problems/minimumspeedtoarriveontime/ class Solution: def minSpeedOnTime(self, dist: List[int], hour: float) > int: n = len(dist) def good(x): t = 0 for i, d in enumerate(dist): if i != n  1: h = math.ceil(d / x) else: h = d / x t += h return t <= hour left, right = 1, 10 ** 7 + 1 while left < right: mid = left + (right  left) // 2 if good(mid): right = mid else: left = mid + 1 return left if left <= 10 ** 7 else 1

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[:n1] { cost += math.Ceil(float64(v) / float64(s)) } cost += float64(dist[n1]) / 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.; 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 } }