Minimum Time to Complete All Deliveries - Video Solutions
Minimum Time to Complete All Deliveries | Leetcode 3733 | Most Optimal Solution
Minimum Time to Complete All Deliveries - Video Solution
Watch 8 video solutions for Minimum Time to Complete All Deliveries, a medium level problem involving Math, Binary Search. This walkthrough by Sanyam IIT Guwahati has 3,189 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
You are given two integer arrays of size 2: d = [d1, d2] and r = [r1, r2].
Two delivery drones are tasked with completing a specific number of deliveries. Drone i must complete di deliveries.
Each delivery takes exactly one hour and only one drone can make a delivery at any given hour.
Additionally, both drones require recharging at specific intervals during which they cannot make deliveries. Drone i must recharge every ri hours (i.e. at hours that are multiples of ri).
Return an integer denoting the minimum total time (in hours) required to complete all deliveries.
Example 1:
Input: d = [3,1], r = [2,3]
Output: 5
Explanation:
- The first drone delivers at hours 1, 3, 5 (recharges at hours 2, 4).
- The second drone delivers at hour 2 (recharges at hour 3).
Example 2:
Input: d = [1,3], r = [2,2]
Output: 7
Explanation:
- The first drone delivers at hour 3 (recharges at hours 2, 4, 6).
- The second drone delivers at hours 1, 5, 7 (recharges at hours 2, 4, 6).
Example 3:
Input: d = [2,1], r = [3,4]
Output: 3
Explanation:
- The first drone delivers at hours 1, 2 (recharges at hour 3).
- The second drone delivers at hour 3.
Constraints:
d = [d1, d2]1 <= di <= 109r = [r1, r2]2 <= ri <= 3 * 104
Approach Overview
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.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Incremental Time Simulation | O(T * n) | O(1) | Conceptual baseline to understand how deliveries accumulate over time |
| Binary Search on Time (Optimal) | O(n log T) | O(1) | Large constraints where direct simulation is too slow |