<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:

    struct node {
        int diff;
        int prof;
        node(int d = 0, int p = 0):diff(d),prof(p) { }
    };

    int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {
        if (profit.size() == 0) return 0;
        vector< node*> jobs;

        // S: O(N) T: O (N)
        int maxDiffJob = 0;
        int maxSkill = 0;
        for (int i = 0; i < profit.size(); i++) {
            jobs.push_back(new node(difficulty[i], profit[i]));
            maxDiffJob = max(maxDiffJob, difficulty[i]);
        }

        for (int i = 0; i < worker.size(); i++)
            maxSkill = max(maxSkill, worker[i]);

        // O(NlogN) to do the sorting. 
//        sort(jobs.begin(), jobs.end(), [](const node* a, const node * b) {
//            return a->diff < b->diff;
//        });

        maxSkill = max(maxDiffJob,maxSkill);

        vector< int> mostProfitable = vector<int>(maxSkill + 1, 0); // size out our vector based on how far we 'care' to go to solve our query. 
        for (int i = 0; i < jobs.size(); i++)
            mostProfitable[ jobs[i]->diff ] = max(mostProfitable[ jobs[i]->diff ], jobs[i]->prof);
        

        // now that we have the most profitable job for EACH SKILL LEVEL identified, lets iterate one more time and keep the most profitble job seen up to that skill level.
        for (int i = 1; i < mostProfitable.size(); i++) 
            mostProfitable[i] = max(mostProfitable[i], mostProfitable[i-1]);
        
        int ans = 0;
        for (int i = 0; i < worker.size(); i++)
            ans += mostProfitable[ worker[i] ];

        return ans;

        
    }
};
54115