python program for weighted job scheduling using dynamic programming and binary search class to represent a job a binary search based function to find the latest job before current job that doesn t conflict with current job index is index of the current job this function returns 1 if all jobs before index conflict with it the array jobs is sorted in increasing order of finish time perform binary search iteratively the main function that returns the maximum possible profit from given array of jobs sort jobs according to finish time create an array to store solutions of subproblems tablei stores the profit for jobs till arri including arri fill entries in table using recursive property find profit including the current job store maximum of including and excluding class to represent a job a binary search based function to find the latest job before current job that doesn t conflict with current job index is index of the current job this function returns 1 if all jobs before index conflict with it the array jobs is sorted in increasing order of finish time perform binary search iteratively the main function that returns the maximum possible profit from given array of jobs sort jobs according to finish time create an array to store solutions of subproblems table i stores the profit for jobs till arr i including arr i fill entries in table using recursive property find profit including the current job store maximum of including and excluding
class Job:
    
    def __init__(self, start, finish, profit):
        self.start = start
        self.finish = finish
        self.profit  = profit

def binary_search(job, start_index):
    

    left = 0
    right = start_index - 1

    
    while left <= right:
        mid = (left + right) // 2
        if job[mid].finish <= job[start_index].start:
            if job[mid + 1].finish <= job[start_index].start:
                left = mid + 1
            else:
                return mid
        else:
            right = mid - 1
    return -1

def schedule(job):
    

    
    job = sorted(job, key = lambda j: j.finish)

    
    
    length = len(job)
    table = [0 for _ in range(length)]

    table[0] = job[0].profit

    
    for i in range(1, length):

        
        incl_prof = job[i].profit
        pos = binary_search(job, i)
        if pos != -1:
            incl_prof += table[pos]

        
        table[i] = max(incl_prof, table[i - 1])

    return table[length-1]