完成旅途的最少时间

Azusa 2024/10/5 力扣每日一题二分查找

难度：中等

给你一个数组 time ，其中 time[i] 表示第 i 辆公交车完成一趟旅途所需要花费的时间。

每辆公交车可以连续完成多趟旅途，也就是说，一辆公交车当前旅途完成后，可以立马开始下一趟旅途。每辆公交车独立运行，也就是说可以同时有多辆公交车在运行且互不影响。

给你一个整数 totalTrips ，表示所有公交车总共需要完成的旅途数目。请你返回完成至少 totalTrips 趟旅途需要花费的最少时间。

示例 1：

输入：time = [1,2,3], totalTrips = 5
输出：3
解释：
- 时刻 t = 1 ，每辆公交车完成的旅途数分别为 [1,0,0] 。
  已完成的总旅途数为 1 + 0 + 0 = 1 。
- 时刻 t = 2 ，每辆公交车完成的旅途数分别为 [2,1,0] 。
  已完成的总旅途数为 2 + 1 + 0 = 3 。
- 时刻 t = 3 ，每辆公交车完成的旅途数分别为 [3,1,1] 。
  已完成的总旅途数为 3 + 1 + 1 = 5 。
所以总共完成至少 5 趟旅途的最少时间为 3 。
示例 2：

输入：time = [2], totalTrips = 1
输出：2
解释：
只有一辆公交车，它将在时刻 t = 2 完成第一趟旅途。
所以完成 1 趟旅途的最少时间为 2 。
 

提示：

1 <= time.length <= 105
1 <= time[i], totalTrips <= 107

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

国庆节期间的题目还真是旅旅又游游啊，又是旅途又是列车又是飞机又是票价的，想着法子提醒你去旅游（doge）

回归正题，一开始看着还是有点懵了，看着样例的旅途数数组，甚至还想到了差分数组，仔细想想完全搭不上边。

然后想到了贪心，但所有公交车都是可以并行开车的，没有先后顺序的问题，也不是一个贪心的问题。

看来看去才发现这是一个二分的问题，我们要找的就是刚好能够完成totalTrips趟旅途的时刻，因为时刻是单调递增的，所以才想到可以用二分来确定时刻。

既然确定了是二分查找，那么就需要确定区间的左右边界，左边界比较随便，直接给个1就好了，而右边界如何确定呢？可以假定为旅途全部都是坐花费时间最多的公交车，即花费旅途时间最多的公交车x旅途数量。

function minimumTime(time: number[], totalTrips: number): number {
    const maxTakeTime = Math.max(...time)
    let l = 1, r = totalTrips * maxTakeTime
    while(l < r) {
      const mid = Math.floor((l + r) / 2) // 时刻
      const trips = calTotalTrips(time, mid)
      if (trips >= totalTrips) {
        r = mid
      } else {
        l = mid + 1
      }
    }
    return r
};

const calTotalTrips = (time, cntTime) => {
  // 计算当前时刻可以完成多少趟旅途
  return time.reduce((pre, cnt) => {
    return pre + Math.floor(cntTime / cnt)
  }, 0)
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

拿下！最近做了挺多二分的题目，有了思路完成起来也比较快，还是有一点进步的。看了下官方解法代码基本一模一样，甚至取上界的方式都一样。

但是看了评论区，其实这个区间范围可以取的更小。左边界可以取花费旅途时间最少的公交车，也就是完成一趟旅途花费的最小时间，大部分时间总比1大嘛。

右边界并不用使用花费旅途时间最多的公交车x旅途数量，而可以采用花费旅途时间最少的公交车x旅途数量，因为无论是花费多少时间的公交车，乘上旅途数量就代表一定能完成这么多趟了，当然取越小越好。

function minimumTime(time: number[], totalTrips: number): number {
    const minTakeTime = Math.min(...time)
    let l = minTakeTime, r = totalTrips * minTakeTime // 缩小区间
    while(l < r) {
        const mid = Math.floor((l + r) / 2) // 时刻
        const trips = calTotalTrips(time, mid)
        if (trips >= totalTrips) {
            r = mid
        } else {
            l = mid + 1
        }
    }
    return r
};

const calTotalTrips = (time, cntTime) => {
    // 计算当前时刻可以完成多少趟旅途
    return time.reduce((pre, cnt) => {
        return pre + Math.floor(cntTime / cnt)
    }, 0)
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

修改之后平均速度快了不少。当然还有更为复杂的取左右边界的方法，可以把区间缩的更小来减少计算次数，但大部分情况也快不了多少了，就这样吧。

时间复杂度：O(nlogU)，其中 n 为 time 的长度，U 为二分上下界之差。在本题数据范围下，U 不会超过 10^14。

Azusa的博客

Choose mode

完成旅途的最少时间

完成旅途的最少时间