<p>You have <code>n</code> jobs and <code>m</code> workers. You are given three arrays: <code>difficulty</code>, <code>profit</code>, and <code>worker</code> where:</p>

<ul>
	<li><code>difficulty[i]</code> and <code>profit[i]</code> are the difficulty and the profit of the <code>i<sup>th</sup></code> job, and</li>
	<li><code>worker[j]</code> is the ability of <code>j<sup>th</sup></code> worker (i.e., the <code>j<sup>th</sup></code> worker can only complete a job with difficulty at most <code>worker[j]</code>).</li>
</ul>

<p>Every worker can be assigned <strong>at most one job</strong>, but one job can be <strong>completed multiple times</strong>.</p>

<ul>
	<li>For example, if three workers attempt the same job that pays <code>$1</code>, then the total profit will be <code>$3</code>. If a worker cannot complete any job, their profit is <code>$0</code>.</li>
</ul>

<p>Return the maximum profit we can achieve after assigning the workers to the jobs.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> difficulty = [2,4,6,8,10], profit = [10,20,30,40,50], worker = [4,5,6,7]
<strong>Output:</strong> 100
<strong>Explanation:</strong> Workers are assigned jobs of difficulty [4,4,6,6] and they get a profit of [20,20,30,30] separately.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> difficulty = [85,47,57], profit = [24,66,99], worker = [40,25,25]
<strong>Output:</strong> 0
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == difficulty.length</code></li>
	<li><code>n == profit.length</code></li>
	<li><code>m == worker.length</code></li>
	<li><code>1 &lt;= n, m &lt;= 10<sup>4</sup></code></li>
	<li><code>1 &lt;= difficulty[i], profit[i], worker[i] &lt;= 10<sup>5</sup></code></li>
</ul>

class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        """
        approach for each worker find the most profitable job they can complete
        we can do this via looking for every job (linear time)
        or via binary search if we sort by difficulty.
        if there are multiple jobs with the same difficulty we want to choose the one with the highest profit
        """
        jobs = [[difficulty[i], -profit[i]] for i in range(len(difficulty))]
        jobs.append([0, 0]) # base case we cant do any job
        jobs.sort()
        numJobs = len(jobs)
        for i in range(1, numJobs):
            jobs[i][1] = min(jobs[i][1], jobs[i-1][1])

        self.ans = 0
        # return the profit for for which difficulty <= ability
        def binsearch(ability):
            low, high = 0, numJobs - 1
            while low < high:
                idx = low + (high - low) // 2
                skill, pay = jobs[idx][0], jobs[idx][1]
                if ability < skill:
                    high = idx
                else:
                    # try to do a more difficult job, but first check that we can do it
                    if idx+1 < numJobs and jobs[idx+1][0] > ability:
                        return pay
                    low = idx + 1
            return jobs[low][1]                

        for w in worker:
            pay = binsearch(w)
            self.ans += pay
        return -1 * self.ans

19400