Maximum Profit Assigning Tasks to Exact-Skill Workers Plus One Wildcard Worker
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
A workshop has a pool of regular workers and a list of tasks. Each worker has an integer skill level, and each task has a required skill level and a profit. A regular worker may take a task only when their skill level is exactly equal to the task's requirement, and each worker can take at most one task.
In addition to the regular workers, one extra worker is available who can take any single task, whatever its requirement.
Each task can be completed at most once, and tasks may be left undone. Return the largest total profit that can be earned by assigning tasks to workers.
### Function Signature
```python
def max_assignment_profit(workers: List[int], tasks: List[List[int]]) -> int:
```
- `workers[i]` is the skill level of regular worker `i`.
- `tasks[j] = [requirement, profit]` describes task `j`.
### Rules
- A regular worker with skill `s` can be assigned only a task whose requirement equals `s`.
- The extra worker can be assigned any one task, or no task.
- No worker takes more than one task, and no task is assigned to more than one worker.
- Idle workers and unassigned tasks are allowed.
- Return a single integer: the maximum achievable sum of the profits of the assigned tasks.
### Constraints
- `1 <= len(workers) <= 10^5`
- `1 <= workers[i] <= 10^9`
- `1 <= len(tasks) <= 10^5`
- `len(tasks[j]) == 2`
- `1 <= tasks[j][0] <= 10^9` and `1 <= tasks[j][1] <= 10^9`
- Several workers may share a skill level, and several tasks may share a requirement.
- The answer can reach about `10^14`, which exceeds `2^31 - 1`; it always stays below `2^53`.
### Examples
**Example 1**
```text
Input: workers = [2, 2, 5], tasks = [[2, 30], [2, 50], [2, 10], [5, 20], [7, 60]]
Output: 160
```
One optimal assignment: the two skill-2 workers take the tasks worth 50 and 30, the skill-5 worker takes the task worth 20, and the extra worker takes the requirement-7 task worth 60, for 50 + 30 + 20 + 60 = 160.
**Example 2**
```text
Input: workers = [4], tasks = [[1, 9]]
Output: 9
```
No regular worker has skill 1, so only the extra worker can earn the 9.
**Example 3**
```text
Input: workers = [3, 3, 3], tasks = [[3, 5]]
Output: 5
```
There is only one task, so the total is 5 no matter who takes it.
Overview: Assign tasks to workers whose skill must exactly equal each task's requirement, with one extra worker who may take any single task, and return the maximum total profit. It tests making the best use of limited workers per skill level, the single wildcard worker, and large sums that exceed 32 bits.
Read the full Amazon Software Engineer interview experience this question came from
