Katkat
Back

Maximum Profit Assigning Tasks to Exact-Skill Workers Plus One Wildcard Worker

AmazonSoftware Engineer · Other
MediumSoftware EngineerOtherCoding & Algorithms

Last updated

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.

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

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

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

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

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.