> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/strings-arrays-and-2-pointers/most-profit-assigning-work.md).

# Most Profit Assigning Work

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

Now we have some workers. `worker[i]` is the ability of the `i`th 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]`

```java
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;
    }
}
```