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).
1using System;
2
3class MinTimeToCompleteTrips {
4 private static bool CanCompleteTrips(int[] time, long t, int totalTrips) {
5 long trips = 0;
6 foreach (int busTime in time) {
7 trips += t / busTime;
8 if (trips >= totalTrips) return true;
9 }
10 return trips >= totalTrips;
11 }
12
13 public static int MinimumTime(int[] time, int totalTrips) {
14 long low = 1, high = (long)1e14;
int result = (int)high;
while (low <= high) {
long mid = low + (high - low) / 2;
if (CanCompleteTrips(time, mid, totalTrips)) {
result = (int)mid;
high = mid - 1;
} else {
low = mid + 1;
}
}
return result;
}
public static void Main(string[] args) {
int[] time = { 1, 2, 3 };
int totalTrips = 5;
Console.WriteLine(MinimumTime(time, totalTrips));
}
}In C#, the solution involves the usual binary search approach where the CanCompleteTrips method determines the feasibility of completing the required trips within a specific time.