# 826. Most Profit Assigning Work

"""
you have n jobs and m workers. you are given three arrays: difficulty,
profit, and worker where difficulty and pofit are the difficulty and profit
of the i'th job and worker is the ability of the jth worker. every worker can
be assigned at most one job, but one job can be completed multiple times.
return the maximum profit we can achieve after assigning the workers to the
jobs.
"""


class Solution(object):
    def maxProfitAssignment(self, difficulty, profit, worker):
        """
        :type difficulty: List[int]
        :type profit: List[int]
        :type worker: List[int]
        :rtype: int
        """
        max_profit_difficulty = []
        info = list(zip(difficulty, profit))
        info.sort(key=lambda x: x[0])
        max_p = 0
        for i in info:
            d, p = i
            max_p = max(max_p, p)
            max_profit_difficulty.append((d, max_p))

        def bin_search(l, upperbound):
            i, j = 0, len(l) - 1
            while i < j:
                mid = (i + j) // 2 + 1
                if l[mid][0] <= upperbound:
                    i = mid
                else:
                    j = mid - 1
            return i

        total_profit = 0
        for w in worker:
            idx = bin_search(max_profit_difficulty, w)
            d, p = max_profit_difficulty[idx]
            if w >= d:
                total_profit += p
        return total_profit


if __name__ == "__main__":
    obj = Solution()
    print(
        obj.maxProfitAssignment(
            difficulty=[2, 4, 6, 8, 10],
            profit=[10, 20, 30, 40, 50],
            worker=[4, 5, 6, 7],
        )
    )
    print(
        obj.maxProfitAssignment(
            difficulty=[85, 47, 57], profit=[24, 66, 99], worker=[40, 25, 25]
        )
    )