Sponsored
Sponsored
This 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.
Time Complexity: O(n log(maxTime)), where 'n' is the number of buses and 'maxTime' is the maximum possible time.
Space Complexity: O(1).
1#include <iostream>
2#include <vector>
3
4bool canCompleteTrips(const std::vector<int>& time, long long t, int totalTrips) {
5 long long trips = 0;
6 for (const int& busTime : time) {
7 trips += t / busTime;
8 if (trips >= totalTrips) return true;
9 }
10 return trips >= totalTrips;
11}
12
13int minimumTime(std::vector<int>& time, int totalTrips) {
14 long long low = 1, high = 1LL * 1e14;
int result = high;
while (low <= high) {
long long mid = low + (high - low) / 2;
if (canCompleteTrips(time, mid, totalTrips)) {
result = mid;
high = mid - 1;
} else {
low = mid + 1;
}
}
return result;
}
int main() {
std::vector<int> time = {1, 2, 3};
int totalTrips = 5;
std::cout << minimumTime(time, totalTrips) << std::endl;
return 0;
}The C++ solution implements a binary search similar to the C version. The canCompleteTrips helper function checks if a certain number of trips can be achieved in given time.