<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 {
public:
    /*
        The idea is to sort jobs in order of increasing difficulty, and workers in order of increasing ability.
        Then, for each worker, we greedily take the best proft job he can do. We use pref_max to keep max profit job till index i, and do upper_bound to find the index till which he can do jobs.
    */
    int maxProfitAssignment(vector<int>& d, vector<int>& p, vector<int>& w) {
        int n=d.size();
        int m=w.size();
        vector<array<int,2>> v(n);
        for(int i=0;i<n;i++)
            v[i]={d[i],p[i]};
        // sort jobs in order of increasing difficulty
        sort(v.begin(),v.end());
        // populate pref max, where pref_max[i] = best profit job till i
        vector<int> pref_max(n,0);
        for(int i=0;i<n;i++)
            pref_max[i]=(i==0?v[i][1]:max(v[i][1], pref_max[i-1]));
        int ans=0;
        const int inf=2e9;
        for(int i=0;i<m;i++)
        {
            // for every worker, we upper_bound to get the index (in) till which he can do jobs. Then we take pref_max[in-1], since that is the best profit job he can do.
            array<int,2> f{w[i],inf};
            int in=upper_bound(v.begin(),v.end(),f)-v.begin();
            if(in)
                ans+=pref_max[in-1];
        }
        return ans;
    }
};
25678