# 1870. Minimum Speed to Arrive on Time

• Time: $O(n\log(r - l))$, where r = 10^7 and l = 1
• Space: $O(1)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 class Solution { public: int minSpeedOnTime(vector& dist, double hour) { int ans = -1; int l = 1; int r = 1e7; while (l <= r) { const int m = (l + r) / 2; if (time(dist, hour, m) > hour) { l = m + 1; } else { ans = m; r = m - 1; } } return ans; } private: double time(const vector& dist, double hour, int speed) { double sum = 0; for (int i = 0; i < dist.size() - 1; ++i) sum += ceil((double)dist[i] / speed); return sum + (double)dist.back() / speed; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 class Solution { public int minSpeedOnTime(int[] dist, double hour) { int ans = -1; int l = 1; int r = (int) 1e7; while (l <= r) { final int m = (l + r) / 2; if (time(dist, hour, m) > hour) { l = m + 1; } else { ans = m; r = m - 1; } } return ans; } private double time(int[] dist, double hour, int speed) { double sum = 0; for (int i = 0; i < dist.length - 1; ++i) sum += Math.ceil((double) dist[i] / speed); return sum + (double) dist[dist.length - 1] / speed; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution: def minSpeedOnTime(self, dist: List[int], hour: float) -> int: ans = -1 l = 1 r = int(1e7) def time(speed: int) -> float: summ = 0 for i in range(len(dist) - 1): summ += math.ceil(dist[i] / speed) return summ + dist[-1] / speed while l <= r: m = (l + r) // 2 if time(m) > hour: l = m + 1 else: ans = m r = m - 1 return ans