Question

2141. Maximum Running Time of N Computers

中文文档

Description

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. The inserted battery can be a totally new battery or a battery from another computer. You may assume that the removing and inserting processes take no time.

Note that the batteries cannot be recharged.

Return _the maximum number of minutes you can run all the _n_ computers simultaneously._

 

Example 1:

Input: n = 2, batteries = [3,3,3]
Output: 4
Explanation: 
Initially, insert battery 0 into the first computer and battery 1 into the second computer.
After two minutes, remove battery 1 from the second computer and insert battery 2 instead. Note that battery 1 can still run for one minute.
At the end of the third minute, battery 0 is drained, and you need to remove it from the first computer and insert battery 1 instead.
By the end of the fourth minute, battery 1 is also drained, and the first computer is no longer running.
We can run the two computers simultaneously for at most 4 minutes, so we return 4.

Example 2:

Input: n = 2, batteries = [1,1,1,1]
Output: 2
Explanation: 
Initially, insert battery 0 into the first computer and battery 2 into the second computer. 
After one minute, battery 0 and battery 2 are drained so you need to remove them and insert battery 1 into the first computer and battery 3 into the second computer. 
After another minute, battery 1 and battery 3 are also drained so the first and second computers are no longer running.
We can run the two computers simultaneously for at most 2 minutes, so we return 2.

 

Constraints:

• 1 <= n <= batteries.length <= 105
• 1 <= batteries[i] <= 109

Solutions

Solution 1

class Solution:
  def maxRunTime(self, n: int, batteries: List[int]) -> int:
    l, r = 0, sum(batteries)
    while l < r:
      mid = (l + r + 1) >> 1
      if sum(min(x, mid) for x in batteries) >= n * mid:
        l = mid
      else:
        r = mid - 1
    return l

class Solution {
  public long maxRunTime(int n, int[] batteries) {
    long l = 0, r = 0;
    for (int x : batteries) {
      r += x;
    }
    while (l < r) {
      long mid = (l + r + 1) >> 1;
      long s = 0;
      for (int x : batteries) {
        s += Math.min(mid, x);
      }
      if (s >= n * mid) {
        l = mid;
      } else {
        r = mid - 1;
      }
    }
    return l;
  }
}

class Solution {
public:
  long long maxRunTime(int n, vector<int>& batteries) {
    long long l = 0, r = 0;
    for (int x : batteries) {
      r += x;
    }
    while (l < r) {
      long long mid = (l + r + 1) >> 1;
      long long s = 0;
      for (int x : batteries) {
        s += min(1LL * x, mid);
      }
      if (s >= n * mid) {
        l = mid;
      } else {
        r = mid - 1;
      }
    }
    return l;
  }
};

func maxRunTime(n int, batteries []int) int64 {
  l, r := 0, 0
  for _, x := range batteries {
    r += x
  }
  for l < r {
    mid := (l + r + 1) >> 1
    s := 0
    for _, x := range batteries {
      s += min(x, mid)
    }
    if s >= n*mid {
      l = mid
    } else {
      r = mid - 1
    }
  }
  return int64(l)
}

function maxRunTime(n: number, batteries: number[]): number {
  let l = 0n;
  let r = 0n;
  for (const x of batteries) {
    r += BigInt(x);
  }
  while (l < r) {
    const mid = (l + r + 1n) >> 1n;
    let s = 0n;
    for (const x of batteries) {
      s += BigInt(Math.min(x, Number(mid)));
    }
    if (s >= mid * BigInt(n)) {
      l = mid;
    } else {
      r = mid - 1n;
    }
  }
  return Number(l);
}

impl Solution {
  #[allow(dead_code)]
  pub fn max_run_time(n: i32, batteries: Vec<i32>) -> i64 {
    // First sort the batteries
    let mut batteries = batteries;
    let m = batteries.len() as i32;
    batteries.sort();

    let mut extra_sum: i64 = 0;
    for i in 0..(m - n) as usize {
      extra_sum += batteries[i] as i64;
    }

    let mut i = (m - n) as usize;
    let mut cur_height = batteries[i];
    let mut ret = cur_height as i64;
    while extra_sum != 0 {
      if i + 1 == (m as usize) {
        assert!(cur_height == *batteries.last().unwrap());
        ret += extra_sum / (n as i64);
        break;
      }

      if batteries[i] == batteries[i + 1] {
        i += 1;
        continue;
      }

      let diff = extra_sum / ((i - ((m - n) as usize) + 1) as i64);

      if (cur_height as i64) + diff <= (batteries[i + 1] as i64) {
        ret = (cur_height as i64) + diff;
        break;
      } else {
        extra_sum -=
          ((batteries[i + 1] - batteries[i]) as i64) *
          ((i - ((m - n) as usize) + 1) as i64);
        ret = batteries[i + 1] as i64;
      }

      i += 1;
      if i != (m as usize) {
        cur_height = batteries[i];
      }
    }

    ret
  }
}