Formatted question description: https://leetcode.ca/all/2187.html

# 2187. Minimum Time to Complete Trips (Medium)

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}

**Similar Questions**:

- Minimum Speed to Arrive on Time (Medium)
- Minimized Maximum of Products Distributed to Any Store (Medium)
- Maximum Running Time of N Computers (Hard)

## Solution 1. Binary Search

This problem is a classic binary search setup – there is a breakpoint `m`

where all `time < m`

are invalid and all `time >= m`

are valid. Here `valid`

means that we can finish at least `totalTrips`

trips given `time`

.

We can check whether a `time`

is valid in `O(N)`

time by traversing `A`

.

```
// OJ: https://leetcode.com/problems/minimum-time-to-complete-trips/
// Time: O(NlogM) where M is the maximum possible answer
// Space: O(1)
class Solution {
public:
long long minimumTime(vector<int>& A, int totalTrips) {
long long L = 1, R = LONG_MAX;
auto valid = [&](long long time) { // returns true if we can finish `totalTrips` trips given `time`
long long sum = 0;
for (long long n : A) {
sum += time / n;
if (sum >= totalTrips) return true;
}
return false;
};
while (L <= R) {
long long M = L + (R - L) / 2;
if (valid(M)) R = M - 1;
else L = M + 1;
}
return L;
}
};
```

## Discuss

https://leetcode.com/problems/minimum-time-to-complete-trips/discuss/1802417/