Given a list of non-negative numbers, we can partition these numbers into at most K groups. We take the sum of each group, then take the max of these sums, and we wish to minimize the largest sum.
f: (nums: List[int], K: int) -> int
For example: Given nums = [1,2,4,5,7,8], K = 3. Result is 9.
Since groups = [[1,8],[2,7],[4,5]], max(1+8,2+7,4+5) = 9
Edge case would be K >= len(nums), since we can put one number each group.
def partition(nums: List[int], K: int) -> int:
'''\
len(nums) >= 1, nums[i] >= 0, K > 0
we partition nums into groups, len(groups) <= K
we wish to minimize max(map(sum, groups))
'''
if K >= len(nums):
return max(nums)
[Solution] As mentioned in comments, there's a subtle difference between this one and the question mentioned as duplicate, so I've coded the solution below.
from typing import *
import math
def partition(lst: List[int], K: int) -> int:
'''\
Time: O(logN * K * N ^ 2), Space: O(N)
logN for binary search, and KN^2 for backtrack search
'''
if K >= len(lst):
return max(lst)
total = sum(lst)
low = math.ceil(total / K)
high = total
def canfit(lst, topbar, K):
groups = [0] * K
is_taken = [False] * len(lst)
def helper(idx_lst, idx_group):
if idx_lst == len(lst):
return True
elif idx_group == len(groups):
return False
else:
for i, num in enumerate(lst):
if not is_taken[i] and groups[idx_group] + num <= topbar:
groups[idx_group] += num
is_taken[i] = True
if helper(idx_lst+1, idx_group):
return True
is_taken[i] = False
groups[idx_group] -= num
if helper(idx_lst, idx_group+1):
return True
return helper(0, 0)
res = None
while low <= high:
mid = (low + high) // 2
if canfit(lst, mid, K):
res = mid
high = mid - 1
else:
low = mid + 1
return res
assert partition([1,4,2,8,5,7], 3) == 9
assert partition([1], 2) == 1
