[LeetCode] 1870. Minimum Speed to Arrive on Time

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 1st train ride takes 1.5 hours, you must wait for an additional 0.5 hours before you can depart on the 2nd 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 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.length
1 <= n <= 105
1 <= dist[i] <= 105
1 <= hour <= 109
There will be at most two digits after the decimal point in hour.

准时到达的列车最小时速。

给你一个浮点数 hour ，表示你到达办公室可用的总通勤时间。要到达办公室，你必须按给定次序乘坐 n 趟列车。另给你一个长度为 n 的整数数组 dist ，其中 dist[i] 表示第 i 趟列车的行驶距离（单位是千米）。
每趟列车均只能在整点发车，所以你可能需要在两趟列车之间等待一段时间。

例如，第 1 趟列车需要 1.5 小时，那你必须再等待 0.5 小时，搭乘在第 2 小时发车的第 2 趟列车。
返回能满足你准时到达办公室所要求全部列车的最小正整数时速（单位：千米每小时），如果无法准时到达，则返回 -1 。

生成的测试用例保证答案不超过 107 ，且 hour 的小数点后最多存在两位数字。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/minimum-speed-to-arrive-on-time
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

思路是二分，而且是在答案上二分。题目最后让我们求的就是最小的时速，那么我们就以时速的上界和下界作为左右边界来进行二分。

在答案上二分的经典题可以参考 875 题，但是这道题有一个坑，就是我们在得到某一个速度，然后去计算用时的时候，for 循环不能直接走到 n，而要走到 n - 1。因为对于 dist 数组里的最后一个元素来说，因为他无需再等下一班车，所以对于最后一趟列车的用时，就是距离 / 速度的结果，无需再进位了。

复杂度

时间O(n * logn)
空间O(n)

代码

Java实现

class Solution {
    public int minSpeedOnTime(int[] dist, double hour) {
        int res = -1;
        int left = 1;
        int right = (int) Math.pow(10, 7);
        while (left <= right) {
            int mid = left + (right - left) / 2;
            double time = helper(dist, mid);
            if (time <= hour) {
                res = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return res;
    }

    private double helper(int[] dist, int speed) {
        double res = 0.0;
        int n = dist.length;
        for (int i = 0; i < n - 1; i++) {
            res += Math.ceil((double) dist[i] / speed);
        }
        res += (double) dist[n - 1] / speed;
        return res;
    }
}

[LeetCode] 1870. Minimum Speed to Arrive on Time

思路

复杂度

代码

相关题目