Minimum Time to Complete Trips

Minimum Time to Complete Trips

What is this problem about?

The Minimum Time to Complete Trips problem gives you a list of buses, each with a fixed time to complete one trip. You need to find the minimum total time for all buses combined to complete at least a given number of total trips. This Minimum Time to Complete Trips coding problem is a textbook example of binary search on the answer, where the answer (time) is searched directly.

Why is this asked in interviews?

Uber, Meta, Amazon, and Google ask this as a standard binary search on the answer problem. It tests whether candidates recognize the monotonic feasibility structure: if time T is sufficient to complete n total trips, then any T' > T is also sufficient. The array and binary search interview pattern is directly applicable, and the problem is clean enough to implement quickly once the insight is found.

Algorithmic pattern used

Binary search on total time. For a given time T, each bus with trip time t can complete floor(T/t) trips. Sum trips across all buses. If the total ≥ required trips, T is feasible. Binary search on T in range [1, max_time * total_trips]. Find the minimum T where the feasibility check passes.

Example explanation

Buses: [1, 2, 3], required trips = 5.

• T = 3: bus 1 → 3 trips, bus 2 → 1 trip, bus 3 → 1 trip. Total = 5 ≥ 5. Feasible.
• T = 2: bus 1 → 2, bus 2 → 1, bus 3 → 0. Total = 3 < 5. Not feasible.
• T = 3 is the minimum time → 3.

Binary search finds this efficiently in O(n log(maxT)) time.

Common mistakes candidates make

• Setting binary search lower bound to 0 (should be 1 — time must be positive).
• Setting upper bound too low — use min(times) * totalTrips as a safe upper bound.
• Integer overflow when computing T * totalTrips (use long/int64).
• Forgetting floor division: trips per bus = T / busTime (integer division).

Interview preparation tip

Minimum Time to Complete Trips is the canonical "binary search on answer" problem for scheduling. Memorize the template: set bounds [low, high], define a check function, run binary search. The check function here is O(n), giving total O(n log(maxT)) complexity — efficient and clean. After mastering this, practice other binary search on answer problems with scheduling: minimum days to finish work, minimum capacity to ship, etc. They all share the same binary search framework.