Maximum running time of n computers

Array Binary Search Greedy Sorting

56.4% acceptance

Feb 25, 2026

2438

You have n computers. You are given the integer n and a 0-indexed integer array batteries where the ith battery can run a computer for batteries[i] minutes. You are interested in running all n computers simultaneously using the given batteries. Initially, you can insert at most one battery into each computer. After that and at any integer time moment, you can remove a battery from a computer and insert another battery any number of times. Return the maximum number of minutes you can run all the n computers simultaneously.

Solution

Rust

Time O(n log n)

Space O(1)

LeetCode

solution.rs

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();
    // Binary search: can all n computers run for T minutes?
    // A battery of capacity b contributes min(b, T) to T time slots
    let mut lo = 0i64;
    let mut hi = total / n;
    while lo < hi {
      let mid = (lo + hi + 1) / 2;
      let supply: i64 = batteries.iter().map(|&b| (b as i64).min(mid)).sum();
      if supply >= n * mid {
        lo = mid;
      } else {
        hi = mid - 1;
      }
    }
    lo
  }
}