Scale Engineer

Minimum Time to Complete Trips

Med
#1992Time: O(Ans * N), where `Ans` is the minimum time required and `N` is the number of buses. In the worst case, `Ans` can be up to `10^7 * 10^7 = 10^14`, which is computationally infeasible.Space: O(1), as we only use a few variables to store the current time and total trips.1 company
Algorithms
Binary Search
Data structures
Array
Companies
Amadeus

Prompt

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

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves checking every possible time value, starting from 1, and incrementing it one by one. For each time t, we calculate the total number of trips that all buses can complete. The first time t for which the total trips is greater than or equal to totalTrips is the minimum time required.

Algorithm

  • Initialize a variable currentTime to 1.
  • Start an infinite loop.
  • Inside the loop, initialize tripsCompleted to 0.
  • Iterate through each busTime in the time array.
  • For each busTime, calculate the trips completed by currentTime as currentTime / busTime and add it to tripsCompleted.
  • After checking all buses, if tripsCompleted is greater than or equal to totalTrips, then currentTime is the minimum time. Return currentTime.
  • If not, increment currentTime and continue the loop.

Walkthrough

The algorithm iterates through time, starting from t = 1. In each iteration, it calculates the total number of trips possible by that time.

To calculate the total trips for a given time t, we iterate through the time array. For each bus i with trip time time[i], the number of trips it can complete is t / time[i]. We sum these values for all buses.

If the calculated total trips is at least totalTrips, we have found our answer, and we return the current time t.

This process continues until the condition is met. However, the maximum possible answer can be very large (up to 10^14), making this approach too slow for the given constraints.

class Solution {    public long minimumTime(int[] time, int totalTrips) {        // This approach is too slow and will time out.        long currentTime = 1;        while (true) {            long tripsCompleted = 0;            for (int t : time) {                // Using long for currentTime to avoid overflow issues, though                // this loop will time out long before overflow becomes a problem.                tripsCompleted += currentTime / t;            }            if (tripsCompleted >= totalTrips) {                return currentTime;            }            currentTime++;        }    }}

Complexity

Time

O(Ans * N), where `Ans` is the minimum time required and `N` is the number of buses. In the worst case, `Ans` can be up to `10^7 * 10^7 = 10^14`, which is computationally infeasible.

Space

O(1), as we only use a few variables to store the current time and total trips.

Trade-offs

Pros

  • Simple to understand and straightforward to implement.

Cons

  • Extremely inefficient due to its linear scan of the time domain.

  • Will result in a 'Time Limit Exceeded' (TLE) error for the given constraints as the answer can be very large.

Solutions

class Solution {public  long minimumTime(int[] time, int totalTrips) {    int mi = time[0];    for (int v : time) {      mi = Math.min(mi, v);    }    long left = 1, right = (long)mi * totalTrips;    while (left < right) {      long cnt = 0;      long mid = (left + right) >> 1;      for (int v : time) {        cnt += mid / v;      }      if (cnt >= totalTrips) {        right = mid;      } else {        left = mid + 1;      }    }    return left;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem