LeetCode 2187 - Minimum Time to Complete Trips

The problem asks us to determine the minimum time required for a fleet of buses to collectively complete a given number of trips. Each bus in the fleet has its own fixed trip duration, denoted by the array time.

leetcodemediumarraybinary-search

LeetCode Problem 2187

Difficulty: 🟡 Medium
Topics: Array, Binary Search

Solution

Problem Understanding

The problem asks us to determine the minimum time required for a fleet of buses to collectively complete a given number of trips. Each bus in the fleet has its own fixed trip duration, denoted by the array time. The buses operate independently and continuously, meaning that a bus can start its next trip immediately after finishing its current trip.

The input consists of an array time of integers, where time[i] represents the time required for bus i to finish one trip, and an integer totalTrips, which represents the total number of trips that all buses must complete. The output is a single integer representing the smallest amount of time required so that the sum of trips completed by all buses is at least totalTrips.

The constraints indicate that time.length can be up to $10^5$ and individual trip times and total trips can be up to $10^7$. This suggests that a naive simulation of every trip is infeasible due to time complexity. Instead, we need an efficient algorithm that avoids iterating over every possible trip individually.

Important edge cases to consider include:

  • Only one bus is available.
  • totalTrips is very small (e.g., 1).
  • Multiple buses have the same trip times.
  • Very large totalTrips with a mix of fast and slow buses.

These edge cases challenge naive implementations and integer handling.

Approaches

A brute-force approach would simulate time incrementally, at each unit of time counting how many trips each bus has completed until the total trips reach totalTrips. While this guarantees correctness, it is too slow. If the fastest bus has a time of 1 and totalTrips is $10^7$, this approach would iterate $10^7$ times, which is not acceptable.

The key observation for a better solution is that the total number of trips completed by a bus at a given time t is simply t // time[i]. This allows us to calculate the total trips across all buses without simulation. Since the total trips is a non-decreasing function of time, we can apply binary search to find the minimum time t such that the sum of trips is at least totalTrips.

Approach Time Complexity Space Complexity Notes
Brute Force O(totalTrips * n) O(1) Incrementally simulate each time unit and count trips
Optimal (Binary Search) O(n log(maxTime * totalTrips)) O(1) Use the non-decreasing property of trips over time to binary search for minimum time

Algorithm Walkthrough

  1. Identify the search space for binary search. The minimum possible time is 1 (or the minimum trip time), and the maximum possible time is min(time) * totalTrips because if the fastest bus does all trips, it would take this long.
  2. Initialize left as 1 and right as min(time) * totalTrips.
  3. While left < right, compute the middle point mid = left + (right - left) // 2.
  4. Calculate the total trips completed at time mid as the sum of mid // time[i] for each bus i.
  5. If the total trips at mid is greater than or equal to totalTrips, update right = mid. Otherwise, set left = mid + 1.
  6. When the loop terminates, left (or right) will hold the minimum time required to complete at least totalTrips.

Why it works: The total number of trips is a non-decreasing function of time. By performing a binary search over possible times, we efficiently find the smallest time that satisfies the condition. The invariant maintained is that left always points to a time that might satisfy the condition, and right always points to a time that definitely satisfies it.

Python Solution

from typing import List

class Solution:
    def minimumTime(self, time: List[int], totalTrips: int) -> int:
        left, right = 1, min(time) * totalTrips
        
        while left < right:
            mid = left + (right - left) // 2
            trips = sum(mid // t for t in time)
            
            if trips >= totalTrips:
                right = mid
            else:
                left = mid + 1
                
        return left

The Python code initializes the search range using the fastest bus multiplied by totalTrips. In each iteration, it computes the number of trips achievable at mid and narrows the search space. The loop terminates when left equals the minimum feasible time.

Go Solution

func minimumTime(time []int, totalTrips int) int64 {
    minTime := time[0]
    for _, t := range time {
        if t < minTime {
            minTime = t
        }
    }

    left, right := int64(1), int64(minTime)*int64(totalTrips)

    for left < right {
        mid := left + (right-left)/2
        var trips int64 = 0
        for _, t := range time {
            trips += mid / int64(t)
        }
        if trips >= int64(totalTrips) {
            right = mid
        } else {
            left = mid + 1
        }
    }
    return left
}

The Go implementation differs slightly due to type handling. We use int64 to prevent overflow when multiplying minTime by totalTrips. The binary search logic is identical.

Worked Examples

Example 1:

time = [1,2,3], totalTrips = 5
Iteration left right mid trips calculation total trips action
1 1 5 3 3//1 + 3//2 + 3//3 = 3+1+1 5 trips >= totalTrips → right = mid
2 1 3 2 2//1 + 2//2 + 2//3 = 2+1+0 3 trips < totalTrips → left = mid+1
3 3 3 - - - loop ends, answer = 3

Example 2:

time = [2], totalTrips = 1
Iteration left right mid trips calculation total trips action
1 1 2 1 1//2 = 0 0 trips < totalTrips → left = 2
2 2 2 - - - loop ends, answer = 2

Complexity Analysis

Measure Complexity Explanation
Time O(n log(maxTime * totalTrips)) Binary search over time range; summing trips over n buses per iteration
Space O(1) Only variables for search bounds and temporary sum are used

The logarithmic factor comes from the search over the time range, which can go up to min(time) * totalTrips. Each check sums over n buses.

Test Cases

# Provided examples
assert Solution().minimumTime([1,2,3], 5) == 3  # Example 1
assert Solution().minimumTime([2], 1) == 2     # Example 2

# Edge and boundary cases
assert Solution().minimumTime([1], 1) == 1  # Single bus, single trip
assert Solution().minimumTime([5,10,2], 10) == 8  # Mixed bus times
assert Solution().minimumTime([10000000], 10000000) == 100000000000000  # Large values
assert Solution().minimumTime([1,1,1], 10000000) == 3333334  # Many buses, small times
assert Solution().minimumTime([2,3,7], 1) == 2  # Only need one trip
Test Why
[1,2,3], 5 Validates multiple buses with different times
[2], 1 Single bus scenario
[1],1 Minimal input size
[5,10,2], 10 Mixed bus speeds for larger trips
[10000000],10000000 Checks handling of very large numbers
[1,1,1],10000000 Tests many fast buses and large totalTrips
[2,3,7],1 Ensures correct answer when only a single trip is needed

Edge Cases

One important edge case is a single bus with a large number of trips. This tests whether the algorithm can handle high values without integer overflow and correctly computes multiples of one bus's trip time.

A second edge case is multiple buses with the same trip time, which could lead to off-by-one errors if the binary search bounds are not handled carefully. The algorithm correctly sums mid // time[i] for each bus, ensuring accurate calculation.

A third edge case is very small totalTrips relative to large bus times, e.g., totalTrips = 1 and `time = [