Problem statement

https://binarysearch.com/problems/Cluster-Management/

Solution

Similar to Leetcode Problem 1655 Distribute Repeating Integers, here we do not need to create counter. Also we need to do a bit of prunning to get AC in python: if mask_sum[mask] > sum(a[i:]): return False means that we can not continue if total time of tasks to finish more than servers avaliable time.

Complexity

It is O(n * 3^m) for time and O(n * 2^m) for space.

Code

class Solution:
    def solve(self, a, customers):
        m = len(customers)
        n = len(a)
        
        mask_sum = [0]*(1<<m)
        for mask, i in product(range(1<<m), range(m)):
            if (1 << i) & mask:
                mask_sum[mask] += customers[i]
                    
        @lru_cache(None)
        def dfs(i, mask):
            if mask == 0: return True
            if i == n:    return False
            
            submask = mask
            if mask_sum[mask] > sum(a[i:]): return False

            while submask:
                if mask_sum[submask] <= a[i] and dfs(i+1, mask ^ submask):
                    return True
                submask = (submask-1) & mask
            return dfs(i+1, mask)
                
        return dfs(0, (1<<m) - 1)