Maximum Running Time of N Computers

Problem Description

Welcome to the world of computer power management, where you can finally answer the age-old question: “How long can I keep my computer running before it decides to take a nap?” The problem at hand is the “Maximum Running Time of N Computers.” Imagine you have a bunch of computers (let’s say N of them) and a collection of batteries. Your mission, should you choose to accept it, is to figure out how long these computers can run before they run out of juice.

Now, if you think this is as easy as charging your phone overnight, think again! The batteries come in different capacities, and you need to distribute the power wisely. It’s like trying to share a pizza with your friends, but some of them are on a diet, and others are just plain greedy.

Solution Code


class Solution {
 public:
  long long maxRunTime(int n, vector& batteries) {
    long sum = accumulate(batteries.begin(), batteries.end(), 0L);

    ranges::sort(batteries);

    while (batteries.back() > sum / n) {
      sum -= batteries.back(), batteries.pop_back();
      --n;
    }

    return sum / n;
  }
};

Approach

The approach taken in this solution is quite clever. First, we calculate the total power available from all the batteries. Then, we sort the batteries to easily access the largest one. If the largest battery has more power than the average power per computer, we can safely remove it from consideration and reduce the number of computers. We repeat this process until the largest battery is no longer greater than the average. Finally, we return the average running time, which is simply the total power divided by the number of computers.

Time and Space Complexity

Time Complexity: O(N log N) due to the sorting of the batteries.
Space Complexity: O(1) since we are using a constant amount of extra space.

Real-World Example

Imagine you’re throwing a party, and you have a limited number of pizzas (batteries) to feed your friends (computers). If one of your friends (the largest battery) can eat more than the average amount of pizza, you might want to send them home early to make sure everyone else gets a slice. By redistributing the pizza wisely, you can ensure that everyone has a good time without anyone going hungry.