Krammer's blog

https://leetcode.com/problems/minimum-speed-to-arrive-on-time/ from Google

Thinking process:

One naive thinking for this is trail and error. Let’s randomly pick a speed and see if we can reach the office in time. If yes, we might be able to decrease the speed because we want to find the minimum speed. This sounds like a binary search. After checking the constraint (10^5), we confirm that binary search is good enough (O(NlogN)).

Here is the code.

 1class Solution {
 2public:
 3    double time(vector<int>& dist, int t) {
 4        double r = 0;
 5        int N = dist.size();
 6        for (int i=0; i<N-1; i++) {
 7            r += ceil((double)dist[i]/t);
 8        }
 9        r += (double)dist[N-1]/t;
10        return r;
11    }
12    int minSpeedOnTime(vector<int>& dist, double hour) {
13        int l = 0, r = 1e7 + 1;
14        while (l < r) {
15            int mid = (l + r) / 2;
16            double t = time(dist, mid);
17            if (t > hour) {
18                l = mid + 1;
19            } else {
20                r = mid;
21            }
22        }
23        if (l == 1e7 + 1) return -1;
24        return l;
25    }
26};

Editorial: LeetCode 1870 Minimum Speed to Arrive on Time