Most Profit Assigning Work

We have jobs: difficulty[i] is the difficulty of the ith job, and profit[i] is the profit of the ith job.

Now we have some workers. worker[i] is the ability of the ith worker, which means that this worker can only complete a job with difficulty at most worker[i].

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

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

What is the most profit we can make?

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 profit of [20,20,30,30] seperately.

Notes:

• 1 <= difficulty.length = profit.length <= 10000

• 1 <= worker.length <= 10000

• difficulty[i], profit[i], worker[i] are in range [1, 10^5]

class Solution {
    static class Pair {
        int diff, profit;

        Pair(int d, int p) {
            diff = d;
            profit = p;
        }
    }

    public int maxProfitAssignment(int[] difficulty, int[] profit, int[] workers) {
        int n = difficulty.length;
        Pair[] jobs = new Pair[n];
        for (int i = 0; i < n; i++)
            jobs[i] = new Pair(difficulty[i], profit[i]);
        Arrays.sort(jobs, (a, b) -> a.diff == b.diff ? b.profit - a.profit : a.diff - b.diff);
        int max = Integer.MIN_VALUE;
        for (int x : difficulty)
            max = Math.max(max, x);
        int[] prefix = new int[max + 1];
        int index = 0;
        max = 0;
        for (int i = 0; i < prefix.length; i++) {
            if (index < jobs.length && i == jobs[index].diff) {
                max = Math.max(max, jobs[index].profit);
                while (index + 1 < jobs.length && jobs[index].diff == jobs[index + 1].diff)
                    index++;
                index++;
            }
            prefix[i] = max;
        }
        int ans = 0;
        for (int worker : workers)
            ans += prefix[worker >= prefix.length ? prefix.length - 1 : worker];

        return ans;
    }
}