Minimum time to complete all deliveries

Math Binary Search

34.6% acceptance

Feb 24, 2026

170

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.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn minimum_time(d: Vec<i32>, r: Vec<i32>) -> i64 {
    // Drone i can deliver in a time slot if the hour is not a multiple of r[i]
    // In the first T hours, drone i can deliver at most: T - floor(T/r[i]) hours
    // But both drones share the hours (only one can deliver per hour).
    // We need: drone 0 gets d[0] of the non-recharge hours, drone 1 gets d[1]
    // Total hours used = d[0] + d[1], and no hour can be both a recharge for drone i and a delivery for drone i.
    // Binary search on T: can we schedule d[0]+d[1] deliveries in T hours?
    // Slots available for drone 0: non-multiples of r[0] in [1,T] = T - T/r[0]
    // Slots available for drone 1: non-multiples of r[1] in [1,T] = T - T/r[1]
    // A slot is available to drone 0 if not multiple of r[0], etc.
    // We need to assign d[0] slots to drone 0 (not mult of r[0]) and d[1] to drone 1 (not mult of r[1])
    // where no slot is assigned to both.
    // Available to both: slots that are neither mult of r[0] nor mult of r[1]
    // Available to only drone 0: mult of r[1] but not r[0]
    // Available to only drone 1: mult of r[0] but not r[1]
    // Must cover: assign some from shared + exclusive slots.
    // Let A0=only-drone0 slots (mult r[1], not mult r[0]), A1=only-drone1 (mult r[0], not mult r[1])
    // AB = available to both (not mult r[0], not mult r[1]), Neither=mult both
    // max delivery possible for drone 0 in T = A0 + AB; for drone 1 = A1 + AB
    // We need d[0] + d[1] <= A0 + A1 + AB (total available, no overlap)
    // AND d[0] <= A0 + AB AND d[1] <= A1 + AB
    let r0 = r[0] as i64;
    let r1 = r[1] as i64;
    let d0 = d[0] as i64;
    let d1 = d[1] as i64;
    fn lcm(a: i64, b: i64) -> i64 {
      fn gcd(a: i64, b: i64) -> i64 { if b == 0 { a } else { gcd(b, a % b) } }
      a / gcd(a, b) * b
    }
    let l = lcm(r0, r1);
    let can = |t: i64| -> bool {
      // multiples of r0 in [1,t]: t/r0
      // multiples of r1: t/r1
      // multiples of lcm: t/l
      let m0 = t / r0; // recharge slots for drone 0
      let m1 = t / r1;
      let m01 = t / l; // both recharge
      // available to drone 0 = t - m0
      // available to drone 1 = t - m1
      // available to both (neither recharges) = t - m0 - m1 + m01
      // available only to drone 0 = m1 - m01
      // available only to drone 1 = m0 - m01
      let avail0 = t - m0; // total slots for drone 0
      let avail1 = t - m1;
      let both = t - m0 - m1 + m01; // slots usable by either
      // Greedy: give exclusive slots first
      let exc0 = m1 - m01; // only drone 0 can use
      let exc1 = m0 - m01; // only drone 1 can use
      if d0 > avail0 || d1 > avail1 { return false; }
      // After using exclusive slots:
      let need0 = (d0 - exc0).max(0); // still needs from shared
      let need1 = (d1 - exc1).max(0);
      need0 + need1 <= both
    };
    let mut lo = 1i64;
    let mut hi = 2 * (d0 + d1) + 2;
    while lo < hi {
      let mid = (lo + hi) / 2;
      if can(mid) { hi = mid; } else { lo = mid + 1; }
    }
    lo
  }
}