[HOT 100] 2187. 完成旅途的最少时间

1. 题目链接


2187. 完成旅途的最少时间 - 力扣（LeetCode）


2. 题目描述


给你一个数组 time ，其中 time 表现第 i 辆公交车完成 一趟旅途 所必要花费的时间。
每辆公交车可以 连续 完成多趟旅途，也就是说，一辆公交车当前旅途完成后，可以 立马开始 下一趟旅途。每辆公交车 独立 运行，也就是说可以同时有多辆公交车在运行且互不影响。
给你一个整数 totalTrips ，表现全部公交车 总共 必要完成的旅途数目。请你返回完成 至少 totalTrips 趟旅途必要花费的 最少 时间。


3. 题目示例


   示例 1 :

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

复制代码

   示例 2 :

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

复制代码

4. 解题思路

• 问题分析
  
  
  
  • 给定多辆车的运输时间数组 time 和总行程数 totalTrips，要求找到最小的总时间 x，使得全部车辆在 x 时间内可以完成至少 totalTrips 次行程。
    
  • 每辆车在时间 x 内能完成的行程数为 x / time（向下取整），总行程数为全部车辆的累加值。
    
  
  
• 二分查找范围
  
  
  
  • 最小可能时间：由最快的车辆决定。比方，最快的车时间为 minT，则最小时间至少为 minT * avg（avg 是平均每个车需完成的行程数）。
    
  • 最大可能时间：由最慢的车或总行程数决定，取 maxT * avg 和 minT * totalTrips 的较小值，以避免无效计算。
    
  
  
• 验证函数（**check**）
  
  
  
  • 对给定的时间 x，计算全部车辆在此时间内能完成的行程数之和。若总和 >= totalTrips，说明时间足够，否则不足。
    
  
  
• 二分过程
  
  
  
  • 不断调解时间范围，找到满足条件的最小值。
    
  
  

5. 题解代码

1. class Solution {
2.     public long minimumTime(int[] time, int totalTrips) {
3.         int minT = Integer.MAX_VALUE;
4.         int maxT = 0;
5.         // 找到最小和最大单次行程时间
6.         for (int t : time) {
7.             minT = Math.min(minT, t);
8.             maxT = Math.max(maxT, t);
9.         }
11.         // 计算平均每个车辆需要完成的行程数（向上取整）
12.         int avg = (totalTrips - 1) / time.length + 1;
14.         // 初始化二分范围
15.         long left = (long) minT * avg - 1;          // 左边界（可能略小于实际最小时间）
16.         long right = Math.min((long) maxT * avg, (long) minT * totalTrips); // 右边界
18.         // 二分查找
19.         while (left + 1 < right) {
20.             long mid = left + (right - left) / 2;
21.             if (check(mid, time, totalTrips)) {
22.                 right = mid; // 时间足够，尝试更小的时间
23.             } else {
24.                 left = mid;  // 时间不足，需要增大
25.             }
26.         }
27.         return right; // 最终 right 是满足条件的最小时间
28.     }
30.     // 验证时间 x 是否足够完成 totalTrips
31.     private boolean check(long x, int[] time, int totalTrips) {
32.         long sum = 0;
33.         for (int t : time) {
34.             sum += x / t; // 当前车辆在 x 时间内能完成的行程数
35.             if (sum >= totalTrips) {
36.                 return true; // 提前终止，优化效率
37.             }
38.         }
39.         return false;
40.     }
41. }

复制代码

6. 复杂度分析

• 时间复杂度：O(n log R)，其中 n 是车辆数，R 是二分范围大小。
  
• 空间复杂度：O(1)，仅利用常数空间。
  

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。