826. Most Profit Assigning Work

You have n jobs and m workers. You are given three arrays: difficulty, profit, and worker where:

• difficulty[i] and profit[i] are the difficulty and the profit of the ith job, and
• worker[j] is the ability of jth worker (i.e., the jth worker can only complete a job with difficulty at most worker[j]).

Every worker can be assigned at most one job, but one job can be completed multiple times.

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

Return the maximum profit we can achieve after assigning the workers to the jobs.

class Solution {
public:
    int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {
        priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> task;
        int gain = 0, res = 0;
        sort(begin(worker), end(worker));
        
        for(int i = 0; i < profit.size(); i++)
            task.push({difficulty[i], profit[i]});
        
        for(auto& w : worker) {
            while(!task.empty() and task.top().first <= w) {
                gain = max(gain, task.top().second);
                task.pop();
            }
            res += gain;
        }
        return res;
    }
};