Minimum Time to Complete All Deliveries - Solution & Explanation

Problem Overview: You are given multiple delivery workers where each worker needs a fixed amount of time to complete one delivery. The task is to compute the minimum total time required for all workers combined to complete a given number of deliveries. Workers can operate in parallel, so the key question becomes: how many deliveries can be finished within a certain time limit?

Approach 1: Incremental Time Simulation (Brute Force) (Time: O(T * n), Space: O(1))

The most direct way is to simulate time from t = 1 upward and repeatedly calculate how many deliveries all workers can complete within that time. For each time value, iterate through the workers and compute t / time[i], which represents how many deliveries that worker can finish. Sum these values until the total deliveries meet or exceed the required amount. While easy to reason about, this approach becomes extremely slow because the minimum valid time T can be very large. You end up checking every possible time value sequentially, which makes the runtime impractical for large constraints.

Approach 2: Binary Search on Time (Optimal) (Time: O(n log T), Space: O(1))

The key observation is monotonicity: if a certain time t is enough to finish all deliveries, then any time greater than t will also work. That property allows you to apply binary search over the answer space. Define a search range between 1 and min(time) * totalDeliveries. For a candidate time mid, iterate through the workers and compute how many deliveries each can complete using mid // time[i]. Add them together. If the total is at least the required number of deliveries, shrink the right boundary because a smaller time might still work. Otherwise, move the left boundary up.

This method avoids simulating each moment in time. Instead, it repeatedly checks feasibility using simple arithmetic. Each feasibility check runs in O(n), and the binary search performs about log T iterations, where T is the maximum possible time. The approach relies on basic math reasoning and efficient boundary reduction from binary search.

Recommended for interviews: Binary search on the answer is the expected solution. Interviewers look for the monotonic property: more time always means more completed deliveries. Starting with a brute force explanation shows you understand the mechanics of the problem, but recognizing the monotonic constraint and switching to binary search demonstrates strong algorithmic intuition.