DeepRest

Maximum Running Time of N Computers

Jan 16th, 2022 (edited)
76
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.97 KB | None | 0 0
  1. '''
  2. Maximum running time depends on the running time of the computer with min capacity battery.
  3. So we need to maximise this limiting factor.
  4. Initially insert batteries greedily into n computers. Then try increasing the min upto the second to min. After that, try increasing both min and second to min together upto third to mon and so on using the remaining capacities to increase the limiting value.
  5. #important note is that the capacities are transferrable(fungible)
  6. '''
  7. class Solution(object):
  8.     def maxRunTime(self, n, batteries):
  9.         """
  10.        :type n: int
  11.        :type batteries: List[int]
  12.        :rtype: int
  13.        """
  14.         batteries.sort()
  15.         capacities = batteries[-n:]
  16.         res = capacities[0]
  17.         rem = sum(batteries)-sum(capacities)
  18.         for i in range(n-1):
  19.             levels = min(rem//(i+1), capacities[i+1]-capacities[i])
  20.             res += levels
  21.             rem -= levels*(i+1)
  22.         res += rem//n
  23.         return res
  24.  
  25.  
Add Comment
Please, Sign In to add comment