Back to main article
LC 2187 Search on Answer Medium

Minimum Time to Complete Trips

Binary search on time. The feasibility check is a single line: sum up how many trips each bus can complete in time t.

Problem

What are we solving?

Problem Statement

You are given an array time where time[i] is the time it takes the i-th bus to complete one trip. Each bus can make multiple trips. Return the minimum time required for all buses together to complete at least totalTrips trips.

Example
Input:time = [1, 2, 3], totalTrips = 5
Output:3
Explanation:At t=3: bus0 does 3 trips, bus1 does 1, bus2 does 1. Total = 5.
Intuition

Binary search on time itself

At time t, bus i completes floor(t / time[i]) trips. Sum all buses — if total ≥ totalTrips, time t is feasible. The function is monotonically increasing in t, so we find the first feasible t with binary search.

time=[1,2,3], totalTrips=5 · Search space: 1..min(time)*totalTrips
condition: sum(t // time[i]) >= totalTrips
t=1F
t=2F
t=3T*
t=4T
t=5T
t=3: bus0→3, bus1→1, bus2→1 = 5 trips total. Minimum feasible time.
→

Upper bound: Use min(time) * totalTrips — this is the time if only the fastest bus ran all trips. The answer is always ≤ this.

Solution

Clean implementation

class Solution {
    public long minimumTime(int[] time, int totalTrips) {
        long left = 1;
        long right = (long) totalTrips * time[0]; // safe upper bound
        for (int t : time) right = Math.min(right, (long) t * totalTrips);
        long boundary = right;

        while (left <= right) {
            long mid = left + (right - left) / 2;
            if (tripsIn(time, mid) >= totalTrips) {
                boundary = mid; right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return boundary;
    }

    private long tripsIn(int[] time, long t) {
        long trips = 0;
        for (int bus : time) trips += t / bus;
        return trips;
    }
}
class Solution:
    def minimumTime(self, time: list[int], totalTrips: int) -> int:
        left = 1
        right = min(time) * totalTrips  # safe upper bound
        boundary = right

        while left <= right:
            mid = left + (right - left) // 2
            if sum(mid // t for t in time) >= totalTrips:
                boundary = mid; right = mid - 1
            else:
                left = mid + 1
        return boundary

Complexity

Time
O(n log T)
T = min(time)*totalTrips. log T iterations, each O(n) feasibility check.
Space
O(1)
Only accumulator variables — no extra structures.
↑ Pattern map