aboutsummaryrefslogtreecommitdiff
path: root/max_running_time_n_computer.cpp
blob: e5a10b557dbd0566a2abb1de6de025f51d490c5e (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// 2141. Maximum Running Time of N Computers
#include "leetcode.h"

/*
 * you have 'n' computers. you are given the integer 'n' and a 0-indexed integer
 * array 'batteries' where the i'th 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 forom another computer. you may assume that the removing and
 * inserting process takes no time. note that the batteries canot be recharged.
 * return the maximum number of minutes you can run all the 'n' computers
 * simultaneously.
 */

class Solution {
public:
  long long maxRunTime(int n, vector<int> &batteries) {
    sort(batteries.begin(), batteries.end());
    long long sum = accumulate(batteries.begin(), batteries.end(), 0L);
    int k = 0, i = batteries.size();
    while (batteries[i - 1 - k] > sum / (n - k))
      sum -= batteries[i - 1 - k++];
    return sum / (n - k);
  }
};

int main() {
  Solution obj;
  vector<int> b1 = {3, 3, 3}, b2 = {1, 1, 1, 1};
  printf("%lld\n", obj.maxRunTime(2, b1)); // expect: 4
  printf("%lld\n", obj.maxRunTime(2, b2)); // expect: 2
}