Tejav
#3733

Minimum Time to Complete All Deliveries

Medium
MathBinary SearchBinary SearchGreedy Algorithms
LeetCode ↗

Approaches

Brute ForceOptimal
Complexity Comparison
Brute ForceOptimal Solution★
Time
O(n²)
O(n log(max(T)))
Space
O(1)
O(1)
💡

Intuition

Time O(n log(max(T)))Space O(1)

Use binary search to find the minimum time required. The key is to calculate how many deliveries can be made in a given time while considering recharge intervals.

⚙️

Algorithm

3 steps
  1. 1Step 1: Define a function to calculate deliveries possible in T hours considering recharge times.
  2. 2Step 2: Use binary search to find the minimum T such that both drones can complete their deliveries.
  3. 3Step 3: The search range is from 0 to the maximum possible time based on deliveries and recharge.
solution.py15 lines
1from math import gcd
2
3def lcm(a, b): return a * b // gcd(a, b)
4
5def canDeliverInTime(T, d, r):
6    deliveries = [T // r[i] + (T % r[i] != 0) for i in range(2)]
7    return deliveries[0] >= d[0] and deliveries[1] >= d[1]
8
9def minTime(d, r):
10    left, right = 0, sum(d) + max(r)
11    while left < right:
12        mid = (left + right) // 2
13        if canDeliverInTime(mid, d, r): right = mid
14        else: left = mid + 1
15    return left
ℹ

Complexity note: The complexity arises from the binary search over time, with a linear check for deliveries in each iteration.

  • 1Recharge times create intervals where drones cannot deliver.
  • 2Binary search efficiently narrows down the minimum time needed.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.