# LeetCode 826: Most Profit Assigning Work

## Problem Restatement

We are given three arrays:

| Array | Meaning |
|---|---|
| `difficulty` | `difficulty[i]` is the difficulty of job `i` |
| `profit` | `profit[i]` is the profit from job `i` |
| `worker` | `worker[j]` is the maximum difficulty worker `j` can handle |

Each worker can do at most one job.

A job can be used more than once. This is important. If three workers all choose the same job, we count that job's profit three times.

If a worker cannot do any job, that worker contributes `0`.

The task is to return the maximum total profit.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Arrays `difficulty`, `profit`, and `worker` |
| Output | Maximum total profit |
| Job rule | Worker can do a job only if `difficulty[i] <= worker[j]` |
| Reuse rule | The same job can be assigned to many workers |

Function shape:

```python
class Solution:
    def maxProfitAssignment(
        self,
        difficulty: list[int],
        profit: list[int],
        worker: list[int],
    ) -> int:
        ...
```

## Examples

Example 1:

```python
difficulty = [2, 4, 6, 8, 10]
profit = [10, 20, 30, 40, 50]
worker = [4, 5, 6, 7]
```

Worker ability `4` can do jobs with difficulty `2` and `4`.

The best profit is `20`.

Worker ability `5` can also do jobs with difficulty `2` and `4`.

The best profit is `20`.

Worker ability `6` can do jobs with difficulty `2`, `4`, and `6`.

The best profit is `30`.

Worker ability `7` can do jobs with difficulty `2`, `4`, and `6`.

The best profit is `30`.

Total:

```python
20 + 20 + 30 + 30 = 100
```

So the answer is:

```python
100
```

Example 2:

```python
difficulty = [85, 47, 57]
profit = [24, 66, 99]
worker = [40, 25, 25]
```

Every job has difficulty greater than every worker's ability.

No worker can do any job.

So the answer is:

```python
0
```

## First Thought: Brute Force

For each worker, check every job.

If the worker can do the job, keep the best profit seen so far.

```python
class Solution:
    def maxProfitAssignment(
        self,
        difficulty: list[int],
        profit: list[int],
        worker: list[int],
    ) -> int:
        total = 0

        for ability in worker:
            best = 0

            for d, p in zip(difficulty, profit):
                if d <= ability:
                    best = max(best, p)

            total += best

        return total
```

This gives the correct answer.

For every worker, it finds the most profitable job that worker can complete.

## Problem With Brute Force

Let:

```python
n = len(difficulty)
m = len(worker)
```

The brute force solution checks every job for every worker.

The time complexity is:

```python
O(n * m)
```

The constraints allow up to `10^4` jobs and `10^4` workers.

That can mean:

```python
10^4 * 10^4 = 10^8
```

checks, which is too much for a clean solution.

We need to avoid restarting the job scan for every worker.

## Key Insight

Sort jobs by difficulty.

Sort workers by ability.

Then process workers from weakest to strongest.

When we reach a worker with ability `ability`, all jobs with difficulty less than or equal to `ability` are available to that worker.

Because workers are sorted, the next worker has equal or greater ability. So any job available to the current worker will also be available to the next worker.

This means we can scan the jobs only once.

While scanning, keep the best profit among all jobs seen so far.

## Algorithm

First, combine each job's difficulty and profit:

```python
jobs = sorted(zip(difficulty, profit))
```

Then sort workers:

```python
worker.sort()
```

Use two variables:

| Variable | Meaning |
|---|---|
| `j` | Index of the next job to consider |
| `best` | Best profit among jobs the current worker can do |

For each worker ability:

1. Add all jobs whose difficulty is at most `ability`.
2. Update `best` with the maximum profit among those jobs.
3. Add `best` to the total answer.

Because the same job can be reused, we do not remove a job after assigning it.

That is why this greedy scan works.

## Walkthrough

Use:

```python
difficulty = [2, 4, 6, 8, 10]
profit = [10, 20, 30, 40, 50]
worker = [4, 5, 6, 7]
```

After sorting jobs:

```python
jobs = [(2, 10), (4, 20), (6, 30), (8, 40), (10, 50)]
```

Workers are already sorted:

```python
worker = [4, 5, 6, 7]
```

Now scan.

For worker `4`, available jobs are:

```python
(2, 10), (4, 20)
```

Best profit is `20`.

Total is now `20`.

For worker `5`, no new jobs become available. Best profit stays `20`.

Total is now `40`.

For worker `6`, job `(6, 30)` becomes available. Best profit becomes `30`.

Total is now `70`.

For worker `7`, no new jobs become available. Best profit stays `30`.

Total is now `100`.

Return:

```python
100
```

## Correctness

We process workers in nondecreasing order of ability.

For any current worker, all jobs with difficulty less than or equal to that worker's ability are feasible.

The pointer `j` advances through the sorted jobs and includes exactly those feasible jobs. Since jobs are sorted by difficulty, once a job has difficulty greater than the current worker's ability, no later job can be feasible for that worker.

The variable `best` stores the maximum profit among all jobs already included.

Therefore, for each worker, `best` is exactly the largest profit among all jobs that worker can complete.

Adding `best` for each worker is valid because each worker can do at most one job, and the same job may be completed multiple times by different workers.

So the algorithm adds the best possible profit for every worker, which gives the maximum total profit.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n log n + m log m)` | Sort jobs and workers |
| Space | `O(n)` | Store paired jobs |

The scan itself is linear:

```python
O(n + m)
```

So sorting dominates the runtime.

## Implementation

```python
class Solution:
    def maxProfitAssignment(
        self,
        difficulty: list[int],
        profit: list[int],
        worker: list[int],
    ) -> int:
        jobs = sorted(zip(difficulty, profit))
        worker.sort()

        total = 0
        best = 0
        j = 0

        for ability in worker:
            while j < len(jobs) and jobs[j][0] <= ability:
                best = max(best, jobs[j][1])
                j += 1

            total += best

        return total
```

## Code Explanation

We first pair each job difficulty with its profit:

```python
jobs = sorted(zip(difficulty, profit))
```

This creates pairs like:

```python
(difficulty, profit)
```

and sorts them by difficulty.

Then we sort the workers:

```python
worker.sort()
```

Sorting workers lets us reuse previous work. When a stronger worker appears, all jobs considered for weaker workers remain possible.

We initialize:

```python
total = 0
best = 0
j = 0
```

`total` stores the answer.

`best` stores the best profit among jobs available so far.

`j` points to the next job that has not been considered yet.

For each worker:

```python
for ability in worker:
```

we add all newly available jobs:

```python
while j < len(jobs) and jobs[j][0] <= ability:
    best = max(best, jobs[j][1])
    j += 1
```

After this loop, `best` is the best profit this worker can earn.

Then we add it:

```python
total += best
```

Finally:

```python
return total
```

returns the maximum total profit.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.maxProfitAssignment(
        [2, 4, 6, 8, 10],
        [10, 20, 30, 40, 50],
        [4, 5, 6, 7],
    ) == 100

    assert s.maxProfitAssignment(
        [85, 47, 57],
        [24, 66, 99],
        [40, 25, 25],
    ) == 0

    assert s.maxProfitAssignment(
        [1, 2, 3],
        [10, 20, 30],
        [3, 3, 3],
    ) == 90

    assert s.maxProfitAssignment(
        [5, 1, 5],
        [50, 10, 60],
        [5],
    ) == 60

    assert s.maxProfitAssignment(
        [10],
        [100],
        [1, 10, 20],
    ) == 200

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| Standard example | Confirms normal behavior |
| No worker can do any job | Confirms profit can be `0` |
| Same job reused | Confirms jobs are reusable |
| Same difficulty with different profits | Confirms we keep maximum profit |
| One job and multiple workers | Confirms repeated assignment works |