Leetcode 2141: Maximum Running Time of N Computers

Pierre-Marie Poitevin
3 min readJan 20, 2022

In this problem, we try to figure out how long we can run n computers using a list of batteries. We have to use n different batteries at any moment and switching them can be done any time (as long as it is a whole minute). Each battery has a set number of minutes that it can be used for.

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.

We are also given a few examples:

Examples

I noticed that the way I solved it is not optimal (takes 95ms to run the test suite), so you might want to check other posts to find faster ways; but I will explain my approach which is pretty effective nonetheless.

The idea is to assign the n larger batteries to each computer. The reason for that is that no matter how I cut it, the largest battery with b cannot be divided to be used in less than b minutes.

Then, I summed all the remaining minutes provided by the remaining batteries, and I try to fill up minutes for each computer, starting with the smallest battery, in order to equalize the amount of time for each computer.

This is shown in the following schema:

Jamboard of the algorithm

This is done in a Map<Long, Integer> valueToCount. This is done because when we equalize, many computers will have the same number of minutes available, so it is shorter to operate on all of them at once.

This is the code I obtained in Java:

class Solution {
public long…

--

--