#2187

Medium

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Minimum Time to Complete Trips

Find the minimum time required for buses to complete at least totalTrips using binary search over time multiples.

Problem Statement

You are given an array time where time[i] represents the time a single bus needs to complete one trip. Each bus can start its next trip immediately after finishing the current one, and all buses operate independently without affecting each other's schedules.

Given an integer totalTrips, determine the minimum time required so that the sum of trips completed by all buses is at least totalTrips. Return this minimum total time as an integer.

Examples

Example 1

Input: time = [1,2,3], totalTrips = 5

Output: 3

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

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

Solution Approach

Binary Search on Time

Treat the total time as a search space. Set low = 1 and high = maximum possible total time. Use binary search to find the smallest time where the cumulative trips of all buses meets or exceeds totalTrips.

Counting Trips Efficiently

For each mid time in binary search, compute trips by summing floor(mid / time[i]) for all buses. This avoids simulating each trip individually and scales to large arrays.

Adjusting Search Boundaries

If the total trips at mid time is less than totalTrips, move the lower boundary up. Otherwise, move the upper boundary down. Continue until low equals high, which will be the minimum required time.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n * log(T)), where n is the number of buses and T is the maximum possible time derived from constraints. Space complexity is O(1) beyond the input array since no extra data structures are needed.

What Interviewers Usually Probe

The candidate quickly identifies binary search over the answer space as the key pattern.
The candidate demonstrates efficient computation of total trips for a given time.
The candidate correctly handles edge cases where buses have varying speeds or only one bus exists.

Common Pitfalls or Variants

Common pitfalls

Attempting to simulate each trip sequentially, which exceeds time limits for large arrays.
Miscalculating the number of trips by not using integer division.
Setting incorrect binary search boundaries that skip the minimum time solution.

Follow-up variants

Find minimum time for buses with cooldown periods between trips.
Compute minimum time when buses have different start times.
Determine minimum time when only a subset of buses can be active at any moment.

FAQ

What is the main pattern used in Minimum Time to Complete Trips?

The problem uses binary search over the valid answer space, treating total time as a search range.

How do I calculate the number of trips completed by all buses in a given time?

Sum floor(time / time[i]) for each bus i to get the total trips completed by that time.

Can this approach handle a single bus with very large totalTrips?

Yes, binary search scales efficiently even when only one bus exists, avoiding direct simulation.

Why not simulate each trip sequentially?

Sequential simulation exceeds time limits for large arrays or high totalTrips, making binary search essential.

What are typical edge cases to watch for?

Single bus, all buses with equal time, and maximum time values near constraints are key edge cases.

terminal

Solution

Solution 1: Binary Search

We notice that if we can complete at least $totalTrips$ trips in $t$ time, then we can also complete at least $totalTrips$ trips in $t' > t$ time. Therefore, we can use the method of binary search to find the smallest $t$.

1

2

3

4

5

6

class Solution:
    def minimumTime(self, time: List[int], totalTrips: int) -> int:
        mx = min(time) * totalTrips
        return bisect_left(
            range(mx), totalTrips, key=lambda x: sum(x // v for v in time)
        )

Continue Practicing

#2179 count good triplets in an array #2226 maximum candies allocated to k children #2141 maximum running time of n computers