826. Most Profit Assigning Work

Problem Statement

Medium

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 i^th job, and
worker[j] is the ability of j^th worker (i.e., the j^th 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.

Example 1:

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

Example 2:

Input: difficulty = [85,47,57], profit = [24,66,99], worker = [40,25,25]
Output: 0

Constraints:

n == difficulty.length
n == profit.length
m == worker.length
1 <= n, m <= 10⁴
1 <= difficulty[i], profit[i], worker[i] <= 10⁵

Java

Source file

class Solution {
    public class Job implements Comparable<Job> {

        public int difficulty;
        public int profit;

        Job(int difficulty, int profit) {
            this.difficulty = difficulty;
            this.profit = profit;
        }

        public boolean canDo(int skill){
            return skill>=this.difficulty;
        }

        @Override
        public int compareTo(Job other) {
            if (this.difficulty == other.difficulty)
                return Integer.compare(other.profit, this.profit);
            return Integer.compare(this.difficulty,other.difficulty);
        }

        @Override
        public String toString() {
            return ("{Difficulty:" + this.difficulty + ", Profit:" + this.profit + "}");
        }
    }

    public int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
        int n = profit.length;
        // Queue<Job> pq = new PriorityQueue<>();
        Job[] jobs = new Job[n];
        for (int i = 0; i < n; i++)
            jobs[i] = new Job(difficulty[i], profit[i]);
        Arrays.sort(jobs);
        // for (Job j: jobs)
        //     System.out.println(j.toString());

        Arrays.sort(worker);
        int ans = 0, i = 0, maxWorth = 0;
        for (int w: worker){
            while(jobs[i].canDo(w)){
                maxWorth = Math.max(maxWorth, jobs[i].profit);
                i++;
            }
            ans += maxWorth;
        }
        return ans;
    }
}