---
# System prepended metadata

title: 2141. Maximum Running Time of N Computers
tags: [Leetcode, Hard, Binary Search]

---

# 2141. Maximum Running Time of N Computers
###### tags: `Leetcode` `Binary Search` `Hard`
Link: https://leetcode.com/problems/maximum-running-time-of-n-computers/
## 思路
核心思想: If the computers cannot run simultaneously for ```a``` minutes, then definitely they cannot run simultaneously for ```b > a``` minutes.
设计canFit(): 
tricky part is the canFit function. If ```sum(min(batteries[i], k)) > n * k```, ```k``` is achievable.
this is true because battery.size > n is always true, so if the ```sum(min(batteries[i], k)) > n * k``` is true, meaning we can always find a way to move the smaller battery's energy on the the top ```n```
所以对于每个battery我们取```min(time, battery)```，然后加总在一起，如果```sum>time*k```说明可以实现

## Code
```java=
class Solution {
    public long maxRunTime(int n, int[] batteries) {
        long batSum = 0;
        for(int battery:batteries) batSum += battery;
        long start = 0;
        long end = batSum/n+1;
        
        while(start<end){
            long mid = start+(end-start)/2;
            if(canFit(n, batteries, mid)){
                start = mid+1;
            }
            else end = mid;
        }
        return start-1;
    }
    private boolean canFit(int n, int[] batteries, long time){
        long timeSum = 0;
        for(int battery:batteries){
            timeSum += Math.min(time, battery);
        }
        return timeSum>=n*time;
    }
}
```