# Most Profit Assigning Work
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/most-profit-assigning-work)
Canonical: https://scaleengineer.com/dsa/problems/most-profit-assigning-work
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [DoorDash](https://scaleengineer.com/companies/doordash), [NetEase](https://scaleengineer.com/companies/netease)
---
## Problem
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.

**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 <= 104`
* `1 <= difficulty[i], profit[i], worker[i] <= 105`

# Approaches
## Brute Force Iteration
This is the most straightforward approach. For each worker, we iterate through all available jobs to find the most profitable job they are capable of completing. The total profit is the sum of the maximum profits for each individual worker.
**Time:** O(n * m), where `n` is the number of jobs and `m` is the number of workers. We have a nested loop structure, iterating through all jobs for each worker. · **Space:** O(1), as we only use a few variables to store the profits, not dependent on the input size.
**Pros:** Simple to understand and implement.; Requires no extra space apart from a few variables.
**Cons:** Highly inefficient for large inputs due to its O(n*m) time complexity.; Likely to cause a 'Time Limit Exceeded' (TLE) error on competitive programming platforms for the given constraints.
### Explanation
The core idea is to consider each worker independently. We initialize a `totalProfit` variable to zero. We then loop through each worker in the `worker` array. Inside this loop, for the current worker, we need to find the best job they can do. We initialize a `maxProfitForWorker` variable to zero. We start another loop that iterates through all the jobs from `i = 0` to `n-1`. In the inner loop, we check if the current worker's ability is greater than or equal to the difficulty of the `i`-th job (`worker[j] >= difficulty[i]`). If the worker can do the job, we compare its profit (`profit[i]`) with the `maxProfitForWorker` found so far for this worker and update `maxProfitForWorker` if the current job's profit is higher. After checking all jobs for the current worker, `maxProfitForWorker` will hold the maximum profit they can earn. We add this amount to our `totalProfit`. After iterating through all workers, `totalProfit` will hold the maximum possible total profit.

```java
class Solution {
    public int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
        int n = difficulty.length;
        int m = worker.length;
        int totalProfit = 0;

        for (int i = 0; i < m; i++) {
            int workerAbility = worker[i];
            int maxProfitForWorker = 0;
            for (int j = 0; j < n; j++) {
                if (workerAbility >= difficulty[j]) {
                    maxProfitForWorker = Math.max(maxProfitForWorker, profit[j]);
                }
            }
            totalProfit += maxProfitForWorker;
        }
        return totalProfit;
    }
}
```
### Algorithm
- Initialize `totalProfit` to 0.
- Iterate through each worker's `ability` in the `worker` array.
- For each worker, initialize `maxProfitForWorker` to 0.
- Start an inner loop to iterate through all jobs.
- If the worker's `ability` is greater than or equal to the job's `difficulty`, update `maxProfitForWorker = max(maxProfitForWorker, current_job_profit)`.
- After checking all jobs for the current worker, add `maxProfitForWorker` to `totalProfit`.
- Return `totalProfit` after iterating through all workers.

## Sorting Jobs and Using Binary Search
This approach improves upon the brute-force method by pre-processing the jobs. We sort the jobs by difficulty and then, for each worker, use binary search to efficiently find the best possible job.
**Time:** O(n log n + m log n). Sorting the jobs takes O(n log n). Then, for each of the `m` workers, we perform a binary search which takes O(log n). · **Space:** O(n) to store the list of `Job` objects.
**Pros:** Significantly more efficient than the brute-force approach.; Handles large inputs within typical time limits.
**Cons:** Requires extra space (O(n)) to store the job objects.; Slightly more complex to implement due to sorting, pre-processing, and binary search logic.
### Explanation
The key observation is that for a given worker, we are interested in the maximum profit among all jobs they are capable of doing. If we sort the jobs by difficulty, we can quickly find the range of jobs a worker can perform. First, we combine the `difficulty` and `profit` arrays into a single data structure, like a list of `Job` objects. We sort this `jobs` list based on difficulty. A crucial step is to pre-process the profits. A worker with ability `w` can do any job with difficulty `d <= w`. To maximize profit, they should pick the job with the highest profit among all these eligible jobs. To handle this, we iterate through the sorted `jobs` and update each job's profit to be the maximum profit seen so far up to that difficulty level. That is, `jobs[i].profit = max(jobs[i-1].profit, jobs[i].profit)`. After this step, the `profit` for a job at index `i` represents the maximum profit for any job with difficulty up to `jobs[i].difficulty`. Now, for each worker, we can perform a binary search on our pre-processed `jobs` list to find the rightmost job whose difficulty is less than or equal to the `workerAbility`. The profit associated with this job is the maximum profit this worker can achieve. We sum up these profits for all workers.

```java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

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

    public int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
        int n = difficulty.length;
        List<Job> jobs = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            jobs.add(new Job(difficulty[i], profit[i]));
        }

        Collections.sort(jobs, (a, b) -> a.difficulty - b.difficulty);

        for (int i = 1; i < n; i++) {
            jobs.get(i).profit = Math.max(jobs.get(i).profit, jobs.get(i - 1).profit);
        }

        int totalProfit = 0;
        for (int ability : worker) {
            int l = 0, r = n - 1, bestProfit = 0;
            while (l <= r) {
                int mid = l + (r - l) / 2;
                if (jobs.get(mid).difficulty <= ability) {
                    bestProfit = jobs.get(mid).profit;
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
            totalProfit += bestProfit;
        }
        return totalProfit;
    }
}
```
### Algorithm
- Create a list of `Job` objects, each with `difficulty` and `profit` attributes.
- Sort the `jobs` list based on `difficulty` in ascending order.
- Pre-process the profits: Iterate through the sorted jobs from the second one and update `jobs[i].profit = max(jobs[i].profit, jobs[i-1].profit)`. This ensures that for any difficulty, the associated profit is the maximum possible up to that point.
- Initialize `totalProfit = 0`.
- For each `ability` in the `worker` array:
  - Use binary search on the `jobs` list to find the rightmost job whose difficulty is less than or equal to the worker's `ability`.
  - If such a job is found at index `j`, its profit `jobs[j].profit` is the maximum profit this worker can get. Add this to `totalProfit`.
  - If no such job exists, the profit for this worker is 0.
- Return `totalProfit`.

## Two Pointers with Sorting
This is the most optimal approach. By sorting both the jobs (by difficulty) and the workers (by ability), we can iterate through them simultaneously using a two-pointer technique to find the maximum profit for each worker in a single pass.
**Time:** O(n log n + m log m). Sorting jobs takes O(n log n), and sorting workers takes O(m log m). The two-pointer traversal takes O(n + m). The sorting steps dominate the complexity. · **Space:** O(n) to store the list of `Job` objects. The space for sorting depends on the implementation but is typically O(log n) or O(n).
**Pros:** Most efficient solution in terms of time complexity.; The main logic after sorting is a single linear scan (O(n+m)), which is very fast.
**Cons:** Requires extra space (O(n)) to store the job objects.; Modifies the order of the input `worker` array by sorting it (if sorting in-place).
### Explanation
The intuition is that if we process workers in increasing order of their ability, the set of jobs they can do is always a superset of the jobs the previous, less-able worker could do. This monotonicity allows for an efficient single-pass solution. First, we combine `difficulty` and `profit` into a list of `Job` objects. We sort this `jobs` list based on `difficulty` and also sort the `worker` array based on ability. We then use two pointers: one for iterating through the sorted workers (`i`) and another for the sorted jobs (`jobIndex`). We also maintain a variable `maxProfitSoFar`. For each worker, we advance the `jobIndex` to include all jobs they can perform, updating `maxProfitSoFar` along the way. The `maxProfitSoFar` for a worker is then added to the `totalProfit`. Since the next worker is more capable, we don't need to reset `jobIndex` or `maxProfitSoFar`, making the process very efficient.

```java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

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

    public int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
        int n = difficulty.length;
        List<Job> jobs = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            jobs.add(new Job(difficulty[i], profit[i]));
        }

        Collections.sort(jobs, (a, b) -> a.difficulty - b.difficulty);
        Arrays.sort(worker);

        int totalProfit = 0;
        int maxProfitSoFar = 0;
        int jobIndex = 0;

        for (int ability : worker) {
            while (jobIndex < n && jobs.get(jobIndex).difficulty <= ability) {
                maxProfitSoFar = Math.max(maxProfitSoFar, jobs.get(jobIndex).profit);
                jobIndex++;
            }
            totalProfit += maxProfitSoFar;
        }

        return totalProfit;
    }
}
```
### Algorithm
- Create a list of `Job` objects, each with `difficulty` and `profit`.
- Sort the `jobs` list by `difficulty`.
- Sort the `worker` array by ability.
- Initialize `totalProfit = 0`, `maxProfitSoFar = 0`, and a job pointer `jobIndex = 0`.
- Iterate through each `ability` in the sorted `worker` array:
  - Use a `while` loop to advance `jobIndex` as long as `jobs[jobIndex].difficulty <= ability`.
  - Inside the `while` loop, update `maxProfitSoFar = max(maxProfitSoFar, jobs[jobIndex].profit)`.
  - After the `while` loop, the current worker can achieve `maxProfitSoFar`. Add this to `totalProfit`.
- Return `totalProfit`.

# Solutions
### Java

```java
class Solution {
public
  int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
    int n = difficulty.length;
    List<int[]> job = new ArrayList<>();
    for (int i = 0; i < n; ++i) {
      job.add(new int[]{difficulty[i], profit[i]});
    }
    job.sort(Comparator.comparing(a->a[0]));
    Arrays.sort(worker);
    int res = 0;
    int i = 0, t = 0;
    for (int w : worker) {
      while (i < n && job.get(i)[0] <= w) {
        t = Math.max(t, job.get(i++)[1]);
      }
      res += t;
    }
    return res;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maxProfitAssignment(vector<int> &difficulty, vector<int> &profit,
                          vector<int> &worker) {
    int n = difficulty.size();
    vector<pair<int, int>> job;
    for (int i = 0; i < n; ++i) {
      job.push_back({difficulty[i], profit[i]});
    }
    sort(job.begin(), job.end());
    sort(worker.begin(), worker.end());
    int i = 0, t = 0;
    int res = 0;
    for (auto w : worker) {
      while (i < n && job[i].first <= w) {
        t = max(t, job[i++].second);
      }
      res += t;
    }
    return res;
  }
};

```

### Python

```python
class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int: n = len(difficulty) job = [(difficulty[i], profit[i]) for i in range(n)] job . sort(key=lambda x: x[0]) worker . sort() i = t = res = 0 for w in worker: while i < n and job[i][0] <= w: t = max(t, job[i][1]) i += 1 res += t return res

```