Maximum Running Time of N Computers

Problem

You have n computers and a list of batteries, each with a charge duration. At any moment each running computer consumes one unit of charge from one battery. You may swap which battery powers which computer at any time — batteries can be shared across computers (but only one computer uses a given battery at any instant).

What is the maximum number of minutes you can keep all n computers running simultaneously?

Intuition

The key insight: a battery with charge b can contribute at most min(b, m) minutes when the target is m, because no single computer can use more than m minutes total, and swapping lets us redistribute excess charge to other computers.

This means m minutes is feasible if and only if sum(min(b_i, m)) >= m * n. The left side is monotonically non-decreasing in m while the right side grows linearly — so there is a threshold where feasibility flips. Binary search finds it.

Upper bound: sum(batteries) / n (total charge evenly distributed). Lower bound: 0 (trivially feasible).

Approach

impl Solution {
    pub fn max_run_time(n: i32, batteries: Vec<i32>) -> i64 {
        let n = n as i64;
        let total: i64 = batteries.iter().map(|&b| b as i64).sum();
        let hi = total / n;

        for m in (0..=hi).rev() {
            let contrib: i64 = batteries.iter().map(|&b| (b as i64).min(m)).sum();
            if contrib >= m * n {
                return m;
            }
        }

        0
    }
}

function maxRunTime(n: number, batteries: number[]): number {
  const total = batteries.reduce((s, b) => s + b, 0);
  const hi = Math.floor(total / n);

  for (let m = hi; m >= 0; m--) {
    const contrib = batteries.reduce((s, b) => s + Math.min(b, m), 0);
    if (contrib >= m * n) return m;
  }

  return 0;
}

impl Solution {
    pub fn max_run_time(n: i32, batteries: Vec<i32>) -> i64 {
        let n = n as i64;
        let total: i64 = batteries.iter().map(|&b| b as i64).sum();

        let mut lo: i64 = 0;
        let mut hi: i64 = total / n;

        while lo < hi {
            let mid= lo + (hi - lo + 1) / 2;
            let contrib: i64= batteries.iter().map(|&b| (b as i64).min(mid)).sum();
            if contrib >= mid * n {
                lo = mid;
            } else {
                hi = mid - 1;
            }
        }

        lo
    }
}

function maxRunTime(n: number, batteries: number[]): number {
  let lo = 0;
  let hi = Math.floor(batteries.reduce((s, b) => s + b, 0) / n);

  while (lo < hi) {
    const mid = lo + Math.ceil((hi - lo) / 2);
    const contrib = batteries.reduce((s, b) => s + Math.min(b, mid), 0);
    if (contrib >= mid * n) {
      lo = mid;
    } else {
      hi = mid - 1;
    }
  }

  return lo;
}

Trace

n = 2, batteries = [3, 3, 3]. Search space [0, 4] (total 9, hi = 9/2 = 4):

Converges at lo = hi = 4.

Edge cases

• One computer — answer is sum(batteries) since all charge feeds one machine.
• n batteries, each = 1 — answer is 1 (each computer gets exactly one minute).
• One massive battery — capped at m contribution; the rest must cover (n-1) * m minutes.
• Overflow — batteries can sum to 10^14; use i64 / safe integer math.

Takeaway

The min(b, m) cap is the key observation. Once you see that a battery's contribution saturates at the target duration, the problem collapses from a scheduling puzzle into a one-line feasibility check — which is monotone, which means binary search.

Same pattern applies to real capacity planning: "given a pool of resources with different sizes, what's the longest all machines can run?" The answer is sum(min(resource, target)) >= target * count.