# Maximum Running Time of N Computers
**Difficulty:** HARD
[External](https://leetcode.com/problems/maximum-running-time-of-n-computers)
Canonical: https://scaleengineer.com/dsa/problems/maximum-running-time-of-n-computers
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [Deutsche Bank](https://scaleengineer.com/companies/deutsche-bank), [Flipkart](https://scaleengineer.com/companies/flipkart)
---
## 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._

**Example 1:**

![](https://assets.glich.co/dsa/maximum-running-time-of-n-computers/image0.png) 

**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:**

![](https://assets.glich.co/dsa/maximum-running-time-of-n-computers/image1.png) 

**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`

# Approaches
## Binary Search on the Answer
A standard approach for problems that ask to maximize a value is to binary search for the answer. We can guess a time `T` and then check if it's possible to run all `n` computers for this duration. The key insight is that if we can run the computers for `T` minutes, we can also run them for any duration less than `T`. This monotonicity allows us to use binary search.

The check function, `canRun(T)`, determines feasibility. To run `n` computers for `T` minutes, we need a total of `n * T` minutes of power. Each battery `b_i` can contribute at most `min(b_i, T)` minutes. Thus, we can run for `T` minutes if the sum of contributions from all batteries is at least the required amount.
**Time:** O(m * log H), where `m` is the number of batteries and `H` is the range of the search space for the answer (from 0 to `sum(batteries)/n`). The `canRun` function takes O(m) time, and it's called O(log H) times by the binary search. · **Space:** O(1), as we only use a few variables to store the search boundaries and the answer.
**Pros:** Conceptually straightforward and a common pattern for optimization problems.; Guaranteed to find the optimal solution due to the monotonic nature of the `canRun` function.
**Cons:** Slightly less efficient than the greedy approach due to the repeated scanning of the batteries array within the binary search loop.
### Explanation
```java
class Solution {
    public long maxRunTime(int n, int[] batteries) {
        long low = 0;
        long high = 0;
        for (int b : batteries) {
            high += b;
        }
        // A reasonable upper bound for the search space.
        // The total time cannot exceed the average time if all power is pooled.
        high /= n;
        
        long ans = 0;
        
        while (low <= high) {
            long mid = low + (high - low) / 2;
            if (canRun(n, batteries, mid)) {
                ans = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return ans;
    }
    
    // Checks if we can run n computers for a given 'time'.
    private boolean canRun(int n, int[] batteries, long time) {
        if (time == 0) return true;
        long totalPowerSupplied = 0;
        // Each battery can supply at most 'time' minutes of power to the system.
        for (int b : batteries) {
            totalPowerSupplied += Math.min((long)b, time);
        }
        // The total power supplied must be at least the total power required.
        return totalPowerSupplied >= (long)n * time;
    }
}
```
### Algorithm
*   The problem asks for the maximum possible running time. This structure suggests that we can use binary search on the answer. If we can run all computers for a time `T`, we can certainly run them for any time `T' < T`. This monotonic property allows for binary search.
*   We need to define a function, let's call it `canRun(time)`, that returns `true` if it's possible to run `n` computers simultaneously for `time` minutes, and `false` otherwise.
*   To determine if `canRun(time)` is true, we consider the total power contribution from all batteries. For a target duration of `time`, a single battery with capacity `b` can contribute at most `min(b, time)` to the total power supply. This is because a battery cannot supply more power than its capacity (`b`), and its contribution is capped at `time` since it can only power one computer at a time.
*   The total power required to run `n` computers for `time` minutes is `n * time`.
*   Therefore, the condition for `canRun(time)` to be true is: `sum(min(battery, time) for battery in batteries) >= n * time`.
*   We can binary search for the largest `time` that satisfies this condition.

**Binary Search Steps:**
1.  Define a search range `[low, high]`. `low` can be `0`. A safe upper bound for `high` can be the sum of all battery capacities divided by `n`, or simply a very large number like `10^14` to be safe.
2.  While `low <= high`:
    a.  Calculate `mid = low + (high - low) / 2`.
    b.  Check if `canRun(mid)` is true.
    c.  If it is, `mid` is a possible answer. We try for a larger time, so we set `ans = mid` and `low = mid + 1`.
    d.  If it's not, `mid` is too large. We need to try a smaller time, so we set `high = mid - 1`.
3.  The final value stored in `ans` will be the maximum possible time.

## Greedy Approach with Sorting
A more efficient solution uses a greedy approach. The intuition is that if we have more batteries than computers, the smallest batteries will inevitably be depleted. We can treat these smallest batteries as a collective power bank. The `n` largest batteries can be assigned to the `n` computers. Then, we use the power from the collective bank to sequentially 'level up' the charge of the computers, starting from the one with the least powerful battery. We continue this process until we run out of extra power or have leveled all computers to the same battery level. The final level represents the maximum running time.
**Time:** O(m log m), where `m` is the number of batteries. The complexity is dominated by the initial sorting of the `batteries` array. The subsequent loops run in O(m) time. · **Space:** O(log m) or O(1), depending on the implementation of the sorting algorithm. `Arrays.sort` in Java for primitives uses a dual-pivot quicksort which has an average space complexity of O(log m).
**Pros:** This is the most efficient approach, with a time complexity dominated by sorting.; It uses constant extra space (if the sort is in-place).
**Cons:** The greedy logic can be less intuitive to come up with compared to the binary search approach.
### Explanation
```java
import java.util.Arrays;

class Solution {
    public long maxRunTime(int n, int[] batteries) {
        // Sort batteries to easily identify the smallest and largest ones.
        Arrays.sort(batteries);
        int m = batteries.length;
        
        // The first m-n batteries are considered extra. Sum their power.
        long extraPower = 0;
        for (int i = 0; i < m - n; i++) {
            extraPower += batteries[i];
        }
        
        // The n largest batteries are at indices m-n to m-1.
        // We will try to level them up using the extra power.
        for (int i = m - n; i < m - 1; i++) {
            // Number of computers we are currently leveling up.
            long numComputers = i - (m - n) + 1;
            // Difference in power to the next level.
            long diff = batteries[i+1] - batteries[i];
            // Power needed to bring all 'numComputers' to the next level.
            long needed = numComputers * diff;
            
            if (extraPower < needed) {
                // Not enough extra power to reach the next level.
                // Distribute the remaining extra power evenly.
                return batteries[i] + extraPower / numComputers;
            }
            
            // Sufficient power, so we level up and decrease extra power.
            extraPower -= needed;
        }
        
        // If we exit the loop, all n computers have been leveled to the
        // capacity of the largest battery. Distribute any remaining extra power.
        return batteries[m-1] + extraPower / n;
    }
}
```
### Algorithm
1.  Sort the `batteries` array in ascending order.
2.  If there are more batteries than computers (`m > n`), the `m-n` smallest batteries can be considered an 'extra' power source. Sum their capacities into a variable `extraPower`.
3.  The remaining `n` largest batteries are our primary power sources, one for each computer. Let's call them `liveBatteries` (which are `batteries[m-n]` to `batteries[m-1]` in the sorted array).
4.  The core idea is to use `extraPower` to 'level up' the `liveBatteries` so they all last for the same amount of time. We iterate through the `liveBatteries` from smallest to largest.
5.  For each `i` from `0` to `n-2`, we calculate the power needed to raise the first `i+1` batteries (which are all conceptually at the level of `liveBatteries[i]`) to the level of the next battery, `liveBatteries[i+1]`. The power needed is `(i+1) * (liveBatteries[i+1] - liveBatteries[i])`.
6.  If `extraPower` is sufficient, we subtract the needed amount and proceed to the next battery.
7.  If `extraPower` is insufficient, we cannot level up to `liveBatteries[i+1]`. The maximum time is the current level `liveBatteries[i]` plus the remaining `extraPower` distributed evenly among the `i+1` computers. The result is `liveBatteries[i] + extraPower / (i+1)`.
8.  If the loop completes, it means we have successfully leveled all `n` batteries to the capacity of the largest one, `liveBatteries[n-1]`. Any remaining `extraPower` can be distributed evenly among all `n` computers. The result is `liveBatteries[n-1] + extraPower / n`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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

```