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 <= 1051 <= time[i], totalTrips <= 107This approach uses binary search to find the minimum time required for the buses to make at least the specified number of trips. The key observation is that if at time `t`, the buses can complete the required trips, then they can also do it in any time greater than `t`. Conversely, if they cannot make the required number of trips at time `t`, then they cannot do it in any lesser time.
We employ binary search with an initial low of 1 and a high value calculated as the maximum possible trip time multiplied by the required total trips. For each midpoint, we calculate the number of trips that all buses can make and adjust the time bounds based on whether the trips meet the requirement or not.
First, we define a helper function canCompleteTrips that verifies if the current time allows the buses to complete the total desired trips. In the main function, we perform binary search on the possible time interval. For each midpoint, we check the fulfillment of the total trips and adjust our search space accordingly.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n log(maxTime)), where 'n' is the number of buses and 'maxTime' is the maximum possible time.
Space Complexity: O(1).
Minimum Time to Complete Trips | Leetcode 2187 | Detailed | codestorywithMIK • codestorywithMIK • 8,572 views views
Watch 9 more video solutions →Practice Minimum Time to Complete Trips with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor