[/dsa/leetcode]

2141 - Maximum Running Time of N Computers

Wednesday, 16 September 2026

<hard> [problem]

Give every battery bigger than the average its own computer, then the remaining batteries can share the remaining computers for exactly total / n minutes.

{greedy}{sortings}

Problem

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.

Input: n = 2, batteries = [3,3,3]
Output: 4

Input: n = 2, batteries = [1,1,1,1]
Output: 2

Constraints:

  • 1 <= n <= batteries.length <= 10^5
  • 1 <= batteries[i] <= 10^9

Approach

Every minute of the run uses n battery-minutes, so the answer is at most total / n. That limit isn’t always reachable, because a battery sits in only one computer at a time. Over a T-minute run it gives at most min(batteries[i], T) minutes, however often it is moved.

Greedy

Sort the batteries and go from the largest down.

  • Battery bigger than total / n: it can power one computer for the entire run by itself, and any charge beyond that is wasted. Give it its own computer and take both out of the problem: total -= arr[i], n--. The average changes, so check the next battery against the new one.
  • Battery at most total / n: every battery after it is smaller, so stop. The answer is total / n.
n = 3, batteries = [1, 2, 2, 7, 10], total = 22
10 > 22 / 3 = 7  ->  own computer   total = 12, n = 2
 7 > 12 / 2 = 6  ->  own computer   total = 5,  n = 1
 2 <= 5 / 1 = 5  ->  stop, answer 5

n never reaches 0. When n == 1, total includes arr[i] itself, so the loop always stops.

class Solution {
public:
    long long maxRunTime(int n, vector<int>& arr) {
        sort(arr.begin(), arr.end());
        long long total = accumulate(arr.begin(), arr.end(), 0LL);

        for (int i = arr.size() - 1; i >= 0; i--) {
            if (arr[i] <= total / n)
                break;
            total -= arr[i];
            n--;
        }

        return total / n;
    }
};
  • time: O(m log m) — sorting m batteries, then one pass
  • space: O(1) — extra space apart from the sort
quantinium © 2026