Maximum Running Time of N Computers

Problem description

You have n computers. You are given the integer n and a 0-indexed integer array batteries where the $i^{th}$ 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.

Constraints

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

Solution

For this kind of problem, we always find it hard to get this extreme value. But if we change a thought, when given the result, can we implement this method? Like in this problem, when given an amount of minutes, can we run all the n computers simultaneously? When the situation changes, this problem is converted into a binary search problem. We can set a left and right boundary of this amount of minutes, and we use binary search to get the final value of our solution.

Thus, how can we determine whether we can run n computers simultaneously when given a special number of minutes? We can set k as the given number of minutes. And for target as the summation number of minutes of n computers.

#define ll long long

ll target = n * k;

And for each battery, it can only choose its maximum volumne of electricity, so each one choose either its volume or k number of minutes for running time.

ll res = 0;
for(int battery: batteries){
    res += battery < k ? battery : k;
        if(res >= target)
            return true;
}

When the result reaches the target number of minutes, it proves that k number of minutes can fit the solution. All of the code shows like this

#define ll long long
class Solution {
public:
    ll maxRunTime(int n, vector<int>& batteries) {
        ll sum = 0;
        for(int battery: batteries)
            sum += battery;
        ll l = 0, r = sum/n;
        while(l < r){
            ll mid = l + (r-l)/2 + 1; // target value rounds up to an integer
            if(canFit(n, mid, batteries)){
                l = mid;
            }else
                r = mid - 1;
        }
        return l;
    }
    
    ll canFit(int n, ll k, vector<int>& batteries){
        ll target = n * k;
        ll res = 0;
        for(int battery: batteries){
            res += battery < k ? battery : k;
                if(res >= target)
                    return true;
        }
        return res >= target;
    }
};

The problem is cited from Leetcode 2141. Maximum Running Time of N Computers. And the solution is cited from [Java] Simple Solution w. Explanation - Chen-Yiyang.