Skip to main content

2141. Maximum Running Time of N Computers

https://leetcode.com/problems/maximum-running-time-of-n-computers/

Python​

class Solution:
    def maxRunTime(self, n: int, batteries: List[int]) -> int:
        def is_remain(time):
            return sum([
                min(time, battery) for battery in batteries
            ]) >= n * time

        left, right = 0, sum(batteries) // n + 1

        while left <= right:
            pivot = (left+right) >> 1
            if is_remain(pivot):
                left = pivot + 1
            else:
                right = pivot - 1
        return right

Go​

Binary Search​

func maxRunTime(n int, batteries []int) int64 {
    isRemain := func(time int64) bool {
		var sum int64 = 0
		for _, battery := range batteries {
			sum += min(time, int64(battery))
		}
		return sum >= int64(n)*time
	}

    var left int64 = 0
    var right int64 = 0
	for _, battery := range batteries {
		right += int64(battery)
	}
	right = right/int64(n) + 1

	for left <= right {
		pivot := (left + right) >> 1
		if isRemain(pivot) {
			left = pivot + 1
		} else {
			right = pivot - 1
		}
	}
	return right
}


func min(a int64, b int64) int64{
	if a < b {
		return a
	}
	return b
}

func max(a int64, b int64) int64 {
	if a > b {
		return a
	}
	return b
}