We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Time to Complete Trips

Number: 2294

Difficulty: Medium

Paid? No

Companies: Meesho, Uber, Amadeus

Problem Description

Given an array time, where time[i] represents the time needed by the iᵗʰ bus to complete one trip, and an integer totalTrips, the objective is to determine the minimum time required so that all buses together can complete at least totalTrips trips. Each bus can perform trips continuously one after another, and the trips on one bus are independent of the trips on another.

Key Insights

  • The total number of trips completed up to a given time t is the sum of t // time[i] for each bus.
  • The relationship between time t and the total trips is monotonic (non-decreasing); if t is enough to satisfy the condition, any time greater than t will also satisfy it.
  • Binary search over the time makes it possible to efficiently find the minimum time t such that the number of trips is at least totalTrips.
  • Set the initial boundaries for binary search: left bound can be 1, and right bound can be max(time) * totalTrips.

Space and Time Complexity

Time Complexity: O(n * log(max(time) * totalTrips)), where n is the length of the time array. Space Complexity: O(1) (excluding the input array storage).

Solution

We use a binary search approach on the time domain. The key idea is to define a helper function that, for a given candidate time t, calculates the total number of trips all buses can complete, which is sum(t // time[i]). With this helper, perform binary search between 1 and max(time) * totalTrips. If the total trips for a candidate time is greater than or equal to totalTrips, then explore lower times, otherwise, move the lower bound upward. This approach efficiently narrows down the minimum time required.

Code Solutions

# Python solution using binary search

def minimumTime(time, totalTrips):
    # Helper function to compute total trips that can be completed within a given time.
    def trips_in_time(t):
        total = 0
        for tbus in time:
            total += t // tbus  # integer division gives number of trips by this bus within time t
        return total

    # Setting initial lower bound and upper bound
    left, right = 1, max(time) * totalTrips
    result = right

    # Binary search for the minimum time
    while left <= right:
        mid = (left + right) // 2
        if trips_in_time(mid) >= totalTrips:
            result = mid               # mid is a valid solution
            right = mid - 1            # try to find a smaller valid time
        else:
            left = mid + 1             # mid does not produce enough trips; increase time
    return result

# Example usage
print(minimumTime([1, 2, 3], 5))  # Output: 3
← Back to All Questions