Maximum Running Time of N Computers LeetCode solution in C++

1
class Solution {
2
 public:
3
  bool canFit(int n, long timeSpan, vector<int> batteries) {
4
    long currBatSum = 0;
5
    long targetBatSum = n * timeSpan;
6
    for (auto it : batteries) {
7
      if (it < timeSpan)
8
        currBatSum += it;
9
      else
10
        currBatSum += timeSpan;
11

12
      if (currBatSum >= targetBatSum) return true;
13
    }
14

15
    return false;
16
  }
17

18
  long long maxRunTime(int n, vector<int> &batteries) {
19
    long totalSum = 0;
20
    long low = *min_element(batteries.begin(), batteries.end());
21

22
    for (auto it : batteries) {
23
      totalSum += it;
24
    }
25

26
    long high = totalSum / n;
27
    long ans = -1;
28

29
    while (low <= high) {
30
      long mid = low + (high - low) / 2;
31
      if (canFit(n, mid, batteries)) {
32
        ans = mid;
33
        low = mid + 1;
34
      } else {
35
        high = mid - 1;
36
      }
37
    }
38
    return ans;
39
  }