2141. Maximum Running Time of N Computers

[mah-shamim]

Topics: Array, Binary Search, Greedy, Sorting, Weekly Contest 276

You have n computers. You are given the integer n and a 0-indexed integer array batteries where the iᵗʰ 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 <= 10⁵
• 1 <= batteries[i] <= 10⁹

Hint:

1. For a given running time, can you determine if it is possible to run all n computers simultaneously?
2. Try to use Binary Search to find the maximal running time

[mah-shamim]

We can use binary search to find the maximum time T such that all n computers can run simultaneously for T minutes. For a given T, we check if the sum of min(batteries[i], T) over all batteries is at least n × T. This condition is necessary and sufficient because each battery can contribute at most T minutes to the total runtime (or its full capacity if less than T), and we can schedule the batteries arbitrarily.

We set the lower bound low = 0 and the upper bound high = ⌊sum(batteries)⌋. Then we perform binary search to find the maximum T that satisfies the condition.

Approach:

• Binary Search on Answer: Since we want the maximum run time, we can perform binary search over possible run times. For a candidate time t, check if it's possible to run all n computers simultaneously for t minutes.
• Feasibility Check: For a given time t, the total energy needed for n computers is n * t. We can use batteries efficiently by:
  • For batteries with capacity >= t: They can power a computer for the full t minutes, and any excess capacity beyond t can be used elsewhere.
  • For batteries with capacity < t: Their entire capacity can be used, but they may need to be combined with other batteries.
• The condition for feasibility is: sum(min(battery, t) for all batteries) >= n * t. This is because:
  • Each battery can contribute at most t minutes towards the total requirement (since we can't use a battery for more than t minutes on a single computer, but can use it across multiple computers through swapping).
  • If the sum of contributions equals or exceeds the total required n * t, then we can achieve t minutes.
• Optimization: Sort batteries if needed, but we can compute the sum without sorting by simply capping each battery's contribution at t and summing them.

Let's implement this solution in PHP: 2141. Maximum Running Time of N Computers

<?php
/**
 * @param Integer $n
 * @param Integer[] $batteries
 * @return Integer
 */
function maxRunTime($n, $batteries) {
    $total = array_sum($batteries);
    $low = 0;
    $high = intdiv($total, $n);

    while ($low < $high) {
        $mid = intdiv($low + $high + 1, 2);
        $required = $n * $mid;
        $sum = 0;
        foreach ($batteries as $b) {
            $sum += min($b, $mid);
            if ($sum >= $required) {
                break;
            }
        }
        if ($sum >= $required) {
            $low = $mid;
        } else {
            $high = $mid - 1;
        }
    }

    return $low;
}

// Test cases
echo maxRunTime(2, [3,3,3]) . "\n";     // Output: 4
echo maxRunTime(2, [1,1,1,1]) . "\n";   // Output: 2
?>

Explanation:

• We use binary search to find the maximum t such that the condition holds.
• The lower bound is 0, and the upper bound is total_sum / n (theoretical maximum if we could use all battery power perfectly).
• At each candidate t, we compute the sum of min(battery, t) for all batteries. If this sum >= n * t, then t is feasible, and we try a larger t. Otherwise, we try a smaller t.
• The binary search converges to the maximum feasible t.

Complexity Analysis

• Time Complexity: O(m log S), where m is the number of batteries and S is the total sum of batteries divided by n. We perform a binary search over the range [0, S], and at each step, we iterate through all batteries to compute the sum.
• Space Complexity: O(1), as we only use a constant amount of extra space.

Solution Walkthrough

1. Compute the total sum of all batteries.
2. Set low = 0 and high = total_sum // n.
3. While low < high:
   • Compute mid as the average of low and high, rounded up.
   • Check if we can run all computers for mid minutes by summing min(battery, mid) for all batteries and comparing with n * mid.
   • If feasible, set low = mid; otherwise, set high = mid - 1.
4. Return low as the maximum run time.

[kovatz]

Thanks for solving the problem of "Maximum Running Time of N Computers"

[mah-shamim]

Thanks