***Painter's Partition Problem

Similar to Allocate Books

Problem Link: https://www.interviewbit.com/old/problems/painters-partition-problem/

class Solution:
    # @param A : integer
    # @param B : integer
    # @param C : list of integers
    # @return an integer
    def paint(self, painters, time, boards):
        
        def partition(boards,maxBoards,painters):
            boardCount=0
            painter=1
            for i in range(len(boards)):
                if(boards[i]>maxBoards):
                    return False
                if(boardCount+boards[i]>maxBoards):
                    painter+=1
                    if(painter>painters):
                        return False
                    boardCount=boards[i]
                else:
                    boardCount+=boards[i]
            return True
            
        def bsearch(boards,l,h,painters):
            if(l<=h):
                mid=(l+h)//2
                if(partition(boards,mid,painters)==True):
                    self.ans=min(self.ans,mid)
                    bsearch(boards,l,mid-1,painters)
                else:
                    bsearch(boards,mid+1,h,painters)
            return self.ans
    
        n=len(boards)
        # if(painters>n):
        #     return -1
        l=max(boards)
        h=sum(boards)
        self.ans=float('inf')
        self.ans=bsearch(boards,l,h,painters)
        return (time*self.ans)%10000003