Minimum Time to Complete Trips — Hard Problem & Solution

Problem statement

Bus i takes time[i] units per trip and starts its next trip immediately. Buses run independently.

Return the minimum time for the fleet to complete at least totalTrips trips in total.

Example 1

Input: time = [1,2,3], totalTrips = 5
Output: 3
Explanation: By t = 3 the buses have done 3, 1 and 1 trips.

Example 2

Input: time = [2], totalTrips = 1
Output: 2

Example 3

Input: time = [5,10,10], totalTrips = 9
Output: 25

Constraints

• 1 <= time.length <= 100000
• 1 <= time[i] <= 1000000
• 1 <= totalTrips <= 1000

How to solve Minimum Time to Complete Trips

Binary search the elapsed time. The fleet's trip count at time t is a simple sum of floors, and it only grows with t, so the first t reaching totalTrips is the answer.

Approach

1. Bound the search by [1, min(time) · totalTrips] — the fastest bus alone always suffices by then.
2. trips(t): sum floor(t / time[i]), stopping early once the target is reached.
3. Binary search the smallest t with trips(t) >= totalTrips.

Why it works

Each bus's trip count is a step function of t, non-decreasing, so their sum is too — the predicate flips exactly once. The upper bound holds because by min(time) · totalTrips the fastest bus has done totalTrips trips on its own, so the fleet has done at least that many.

Complexity

• Time — O(n log(min(time) · totalTrips))
• Space — O(1)

Pitfalls

• The partial sums reach 10^5 · 10^9 before the early exit — accumulate in 64-bit or stop as soon as the target is met.
• Searching up to the slowest bus times totalTrips still works but wastes iterations.
• Buses are independent; there is no scheduling to do.

Reference solution

Python

from typing import List

def minimumTime(time: List[int], totalTrips: int) -> int:
    lo, hi = 1, min(time) * totalTrips

    def trips(t: int) -> int:
        c = 0
        for x in time:
            c += t // x
            if c >= totalTrips:
                return c
        return c

    while lo < hi:
        mid = (lo + hi) // 2
        if trips(mid) >= totalTrips:
            hi = mid
        else:
            lo = mid + 1
    return lo

JavaScript

var minimumTime = function(time, totalTrips) {
    var fastest = time[0], i;
    for (i = 1; i < time.length; i++) if (time[i] < fastest) fastest = time[i];
    var trips = function(t) {
        var c = 0;
        for (var j = 0; j < time.length; j++) {
            c += Math.floor(t / time[j]);
            if (c >= totalTrips) return c;
        }
        return c;
    };
    var lo = 1, hi = fastest * totalTrips;
    while (lo < hi) {
        var mid = Math.floor((lo + hi) / 2);
        if (trips(mid) >= totalTrips) hi = mid; else lo = mid + 1;
    }
    return lo;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Count Ways to Make Array With Product Hard
• The Number of Good Subsets Hard
• Number of Ways to Reorder Array to Get Same BST Hard
• Make Array Strictly Increasing Hard
• Odd Even Jump Hard
• Maximum Number of Events That Can Be Attended II Hard