2187. Minimum Time to Complete Trips LeetCode Solution

In this guide, you will get 2187. Minimum Time to Complete Trips LeetCode Solution with the best time and space complexity. The solution to Minimum Time to Complete Trips problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Minimum Time to Complete Trips solution in C++
Minimum Time to Complete Trips solution in Java
Minimum Time to Complete Trips solution in Python
Additional Resources

2187. Minimum Time to Complete Trips LeetCode Solution image

Problem Statement of Minimum Time to Complete Trips

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

Complexity Analysis

Time Complexity: O(n\log (\min(\texttt{time}) \cdot \texttt{totalTrips}))
Space Complexity: O(1)

2187. Minimum Time to Complete Trips LeetCode Solution in C++

class Solution {
 public:
  long long minimumTime(vector<int>& time, int totalTrips) {
    long l = 1;
    long r = static_cast<long>(ranges::min(time)) * totalTrips;

    while (l < r) {
      const long m = (l + r) / 2;
      if (numTrips(time, m) >= totalTrips)
        r = m;
      else
        l = m + 1;
    }

    return l;
  }

  long numTrips(const vector<int>& times, long m) {
    return accumulate(times.begin(), times.end(), 0L,
                      [&](long subtotal, int t) { return subtotal + m / t; });
  }
};
/* code provided by PROGIEZ */

2187. Minimum Time to Complete Trips LeetCode Solution in Java

class Solution {
  public long minimumTime(int[] time, int totalTrips) {
    long l = 1;
    long r = Arrays.stream(time).min().getAsInt() * (long) totalTrips;

    while (l < r) {
      final long m = (l + r) / 2;
      if (numTrips(time, m) >= totalTrips)
        r = m;
      else
        l = m + 1;
    }

    return l;
  }

  private long numTrips(int[] time, long m) {
    return Arrays.stream(time).asLongStream().reduce(0L, (subtotal, t) -> subtotal + m / t);
  }
}
// code provided by PROGIEZ

2187. Minimum Time to Complete Trips LeetCode Solution in Python

class Solution:
  def minimumTime(self, time: list[int], totalTrips: int) -> int:
    l = 1
    r = min(time) * totalTrips

    while l < r:
      m = (l + r) // 2
      if sum(m // t for t in time) >= totalTrips:
        r = m
      else:
        l = m + 1

    return l
 # code by PROGIEZ