< Back





2187. Minimum Time to Complete Trips

We're given a list of buses where time[i] is the time it takes for a bus to complete a trip. We need
to complete totalTrips trips. We're asked to find the minimum time to reach total trips given our
buses.

We need to think - for a given time t, how do we determine how many trips are taken across all our
buses? Well, we know that number of trips for a particular bus is t // time[i]. So for each bus and
a time, t, we can calculate the number of trips that can be taken by all buses for that time.

Next, we want to find the minimum time that is at least, so greater than or equal to, totalTrips. We
use binary search to create an upper and lower bound to find this minimum, using the minimum
time[i] as the lower bound and min(time[i]) * totalTrips as the upper bound. We choose these bounds
because the fastest we can move is min(time[i]) and the slowest we can move is
min(time[i]) * totalTrips.

During each iteration of binary search, for a given time, m, we calculate the number of trips that
can be taken across all buses. If the number of trips is less than totalTrips, we set the lower bound
to m + 1. If the number of trips is greater than or equal to totalTrips, we set the upper bound to m.

Eventually, we find the minimum time that is at least totalTrips and return it.

The solution is as follows:


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

          while l < r:
              m = (r + l) // 2

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

          return l


_ Time Complexity:

  O(m log(n)) - Where m is the number of buses and n is totalTrips.

_ Space Complexity:

  O(1) - We use a constant amount of space.