You are given an array `time`

where `time[i]`

denotes the time taken by the `i`

bus to complete ^{th}**one trip**.

Each bus can make multiple trips **successively**; that is, the next trip can start **immediately after** completing the current trip. Also, each bus operates **independently**; that is, the trips of one bus do not influence the trips of any other bus.

You are also given an integer `totalTrips`

, which denotes the number of trips all buses should make **in total**. Return *the minimum time required for all buses to complete at least *

`totalTrips`

*trips*.

**Example 1:**

Input:time = [1,2,3], totalTrips = 5Output:3Explanation:- At time t = 1, the number of trips completed by each bus are [1,0,0]. The total number of trips completed is 1 + 0 + 0 = 1. - At time t = 2, the number of trips completed by each bus are [2,1,0]. The total number of trips completed is 2 + 1 + 0 = 3. - At time t = 3, the number of trips completed by each bus are [3,1,1]. The total number of trips completed is 3 + 1 + 1 = 5. So the minimum time needed for all buses to complete at least 5 trips is 3.

**Example 2:**

Input:time = [2], totalTrips = 1Output:2Explanation:There is only one bus, and it will complete its first trip at t = 2. So the minimum time needed to complete 1 trip is 2.

**Constraints:**

`1 <= time.length <= 10`

^{5}`1 <= time[i], totalTrips <= 10`

^{7}

**Solution: Binary Search**

Find the smallest t s.t. trips >= totalTrips.

Time complexity: O(nlogm), where m ~= 1e15

Space complexity: O(1)

## C++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
// Author: Huahua class Solution { public: long long minimumTime(vector<int>& time, int totalTrips) { long long l = 1; long long r = 1e15; while (l < r) { long long m = l + (r - l) / 2; long long trips = 0; for (int t : time) { trips += m / t; if (trips >= totalTrips) break; } if (trips >= totalTrips) r = m; else l = m + 1; } return l; } }; |

请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。

如果您喜欢这篇文章／视频，欢迎您捐赠花花。

If you like my articles / videos, donations are welcome.

## Be First to Comment