2187. Minimum Time to Complete Trips
Description
You are given an array time
where time[i]
denotes the time taken by the ith
bus to complete 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 = 5 Output: 3 Explanation: - 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 = 1 Output: 2 Explanation: 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 <= 105
1 <= time[i], totalTrips <= 107
Solutions
Solution 1: Binary Search
We notice that if we can complete at least $totalTrips$ trips in $t$ time, then we can also complete at least $totalTrips$ trips in $t' > t$ time. Therefore, we can use the method of binary search to find the smallest $t$.
We define the left boundary of the binary search as $l = 1$, and the right boundary as $r = \min(time) \times totalTrips$. For each binary search, we calculate the middle value $\textit{mid} = \frac{l + r}{2}$, and then calculate the number of trips that can be completed in $\textit{mid}$ time. If this number is greater than or equal to $totalTrips$, then we reduce the right boundary to $\textit{mid}$, otherwise we increase the left boundary to $\textit{mid} + 1$.
Finally, return the left boundary.
The time complexity is $O(n \times \log(m \times k))$, where $n$ and $k$ are the length of the array $time$ and $totalTrips$ respectively, and $m$ is the minimum value in the array $time$. The space complexity is $O(1)$.
1 2 3 4 5 6 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
|
1 2 3 4 5 6 7 8 9 10 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|