2141

2141. Maximum Running Time of N Computers (Hard)

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

Companies: Deutsche Bank

Related Topics:
Array, Binary Search, Greedy, Sorting

Similar Questions:

• Minimum Moves to Equal Array Elements (Medium)
• Sell Diminishing-Valued Colored Balls (Medium)
• Maximum Number of Tasks You Can Assign (Hard)
• Minimum Time to Complete Trips (Medium)
• Minimum Amount of Time to Fill Cups (Easy)

Solution 1.

Solution

---

Overview

From the first example, let's try another distribution plan first. Suppose we let 2 batteries support 2 computers continuously, we will end up with 2 empty batteries and 1 full battery. Then the running time is fixed at 3 since we can't use the only battery left to support 2 computers simultaneously.

It implies that there is a strategy to distribute the batteries properly. Let's move on to finding the best patterns.

---

Approach 1: Sorting and Prefix Sum

Intuition

First, we simplify the original problem a little bit:

Suppose we have 4 computers (named A, B, C and D) and have to pick exactly 4 batteries. What is the maximum running time?

This is quite straightforward. We just pick the largest 4 batteries and let them support these 4 computers separately (let's call the list that contains these 4 batteries live), and the running time is determined by the smallest battery picked.

What if we are allowed to pick a 5th battery?

Let's pick the largest battery that isn't in use. Clearly, the smallest of these 4 batteries will be the bottleneck, so we use the power in the 5th battery to increase the running time of computer A that has the smallest battery.

What if we are allowed to pick more batteries?

We can freely use every battery except the largest 4 to increase the total running time. Because we can freely swap batteries in 0 time, all the extra power is interchangeable. We can take this extra power and "transfer" it to the batteries in live. Let extra be the sum of all the extra power.

Let's say live is sorted. We try using some of our extra power to increase live[0] running time to live[1]. In the process, extra -= live[1] - live[0].

Now, live[0] = live[1]. Can we continue? We try increasing the running time to live[2]. However, not only would we need to increase live[1] to live[2], we also need to increase live[0] to live[2] so it doesn't bottleneck the running time. We already spent some power to increase live[0] to live[1], so we just need to spend twice as much power as the difference live[2] - live[1].

Now we have live[0] = live[1] = live[2]. If we want to increase the running time to live[3], we need to spend three times as much power as the difference (live[3] - live[2]).

Oops, seems we are running out of extra power before reaching live[3], so the bottleneck is decided by live[2]. We have some extra power remaining, so we do our best to increase the running time by evenly splitting the remaining power to the computers (extra / 3).

What if we have an example where extra is large enough to support all batteries in live becoming equal to live[n - 1]. Any remaining power in extra should similarly be evenly split across all the computers to increase the final running time. The final running time is determined by live[n - 1] plus the extra running time we can make using extra power, which is extra / n.

To generalize, at each battery live[i], if we want to increase the running time to live[i + 1], we need to spend (i + 1) times as much power as (live[i + 1] - live[i]). With this formula, we don't actually need to update the values of live. Since after each iteration, we already know that live[0] = live[1] = ... = live[i].

We iterate through live until we either cannot afford to increase to live[i + 1] anymore, or we manage to iterate through the entire array. In both cases, we do our best to evenly allocate the remaining extra power.

You may be thinking that in the case below, since there is some unused power in the larger batteries (like the largest battery on the right), can we further increase the total running time using this unused power? The answer is NO.

As shown in the following picture, suppose we do allocate the power "equally" by using the excess power of the largest battery (colored in red) on other computers. It means that there are times when the red battery is used on other computers, but the same battery also supports the computer D all the time. This contradicts the rule that one battery can't support more than one computer at the same time.

Therefore, we observe the pattern that:

If a battery batteries[i] has more power than the total running time, there is no way we can use its excess power to further increase the running time. Therefore, once we have picked the largest n batteries and assign them to n computers, these batteries are tied to their computer and swapping them does not bring any longer running time.

Algorithm

1. Sort batteries.

2. Find the largest n batteries and assign them to n computers, these n batteries are exclusively used by each computer and cannot be shared with other computers. Create an array live that contains the largest n batteries in sorted order, which represents the n computers.

3. Sum up the power of the remaining batteries as extra.

4. Iterate over live from 0 to n - 2, for each index i:

   • If extra power can increase the running time of the first i computers from live[i] to live[i + 1], then we subtract the required power from extra and move on to the next index.
   • Otherwise, we have to stop at this point and return live[i] + extra / (i + 1).

5. If there is still power left after the iteration, it means we can further increase the total running time of n computers from live[n - 1] by extra / n. Therefore, return live[n - 1] + extra / n.

Complexity Analysis

Let mmm be the length of the input array batteries.

• Time complexity: O(m⋅log⁡m)O(m \cdot\log m)O(m⋅logm)

  • We sort batteries\text{batteries}batteries in place, it takes O(m⋅log⁡m)O(m \cdot\log m)O(m⋅logm) time.

  • Picking the largest n-th batteries from a sorted array takes O(n)O(n)O(n) time. Note that since n<mn < mn<m, this term will be dominated.

  • Then we iterate over the remaing part of the batteries, the computation at each step takes constant time. Thus it takes O(m)O(m)O(m) time to finish the iteration.

  • To sum up, the overall time complexity is O(m⋅log⁡m)O(m \cdot\log m)O(m⋅logm).

• Space complexity: O(m)O(m)O(m)

  • Some extra space is used when we sort batteries\text{batteries}batteries in place. The space complexity of the sorting algorithm depends on the programming language.
    • In python, the sort method sorts a list using the Timsort algorithm, which is a combination of Merge Sort and Insertion Sort and uses O(m)O(m)O(m) additional space.
    • In Java, Arrays.sort() is implemented using a variant of the Quick Sort algorithm which has a space complexity of O(log⁡m)O(\log m)O(logm).
  • We create an array of size O(n)O(n)O(n) to record the power (running time) of each computer.
  • To sum up, the overall space complexity is O(m)O(m)O(m).

// OJ: https://leetcode.com/problems/maximum-running-time-of-n-computers
// Author: github.com/lzl124631x
// Time: O(NlogN)
// Space: O(1)
class Solution {
public:
    long long maxRunTime(int n, vector<int>& A) {
        sort(begin(A), end(A));
        long long N = A.size(), extra = accumulate(begin(A), end(A) - n, 0LL), start = N - n, ans = 
A[start];
        for (int i = start, len = 1; i < N - 1; ++i, ++len) {
            long long d = A[i + 1] - A[i];
            if (extra < len * d) return A[i] + extra / len;
            extra -= len * d;
        }
        return A.back() + extra / n;
    }
};

Solution 2. Binary Search

Intuition

In the previous approach, we began by selecting the largest n batteries (one for each computer) and then assigning the remaining power extra to these computers using a greedy approach until we reach the longest running time.

Alternatively, we can first set a target running time, target, then try to reach this running time using all batteries.

Here we still take advantage of the conclusion we reached at the end of the previous approach (Please refer to the previous approach):

• If the power of a battery is smaller than target, we can use all of its power.
• If the power of a battery is larger than target, we can only use target power from it.

Therefore, we can traverse through batteries and collect all the power that can be used. If the sum of collected power is larger than or equal to target * n, all computers can run for target time.

As shown in the picture above, suppose we set a running time target, then we collect power from all batteries (colored in green). Finally, we check if the sum of the collected power is larger than or equals to target * 2.

How to find the largest running time?

Instead of trying every target from 1 until finding the largest possible running time, we can take advantage of binary search to locate the largest target faster than linear search.

Initially, we set the left boundary as 1 as the minimum possible running time. Assuming we can use all the power perfectly, the maximum running time is sum(batteries) / n, so we set the right boundary as sum(batteries) / n. As a result, the largest target is limited to the inclusive range [left, right], and we can apply binary search in this range to find it.

Algorithm

1. Initialize the boundaries of the search space as left = 1, and right = sum(batteries) / n.

2. While left < right:

   • Find the middle value target = right - (right - left) / 2.
   • Check if batteries can support n computers run target time. Iterate over batteries and record extra, the accumulative sum of min(batteries[i], target).

3. Check if extra >= n * target:

   • If so, set left = target and repeat step 2.
   • Otherwise, set right = target - 1 and repate step 2.

4. Once the binary search ends, return left.

Complexity Analysis

Let mmm be the length of the input array batteries and kkk be the maximum power of one battery.

• Time complexity: O(m⋅log⁡k)O(m \cdot\log k)O(m⋅logk)

  • Initially, we set 1 as the left boundary and sum(batteries) / n as the right boundary. Thus it takes O(log⁡(m⋅kn))O(\log (\frac{m\cdot k}{n}))O(log(nm⋅k​)) steps to locate the maximum running time in the worst-case scenario.

  • At each step, we need to iterate over batteries to add up the power that can be used, which takes O(m)O(m)O(m) time.

  • Therefore, the overall time complexity is O(m⋅log⁡(m⋅kn))=O(m⋅log⁡k)O(m \cdot\log (\frac{m\cdot k}{n})) = O(m\cdot \log k)O(m⋅log(nm⋅k​))=O(m⋅logk)
    ,k≫m,n, k \gg m, n,k≫m,n

• Space complexity: O(1)O(1)O(1)

  • During the binary search, we only need to record the boundaries of the searching space and the power extra, and the accumulative sum of extra, which only takes constant space.

// OJ: https://leetcode.com/problems/maximum-running-time-of-n-computers
// Author: github.com/lzl124631x
// Time: O(NlogN)
// Space: O(1)
class Solution {
public:
    long long maxRunTime(int n, vector<int>& A) {
        long long sum = accumulate(begin(A), end(A), 0LL), L = 1, R = sum / n;
        auto valid = [&](long long target) {
            long long extra = 0;
            for (int n : A) extra += min((long long)n, target);
            return extra >= n * target;
        };
        while (L <= R) {
            long long M = L + (R - L) / 2, extra = 0;
            if (valid(M)) L = M + 1;
            else R = M - 1;
        }
        return R;
    }
};