Tap here to switch tabs
Problem
Submissions

Problem: Maximize Profit from Task Assignment

Maximize Profit from Task Assignment matches workers to one distinct task each when skill levels exactly meet requirements, with one extra worker able to take any task; return the greatest total profit.

Statement

You are given an integer array workers and a two dimensional integer array tasks, where tasks[i] = [requirement_i, profit_i] indicates that the iextthi^{ ext{th}} task requires an exact skill level of requirement_i and yields a profit of profit_i.

Each worker in workers has a skill level equal to workers[i] and can complete at most 11 task whose skill requirement exactly matches workers[i].

In addition, there is 11 extra worker who can complete any single task without any skill requirement.

Each task can be completed at most once by at most 11 worker.

Return the maximum total profit that can be obtained from completing the tasks.

Constraints:

  • 1≤1 \leq workers.length ≤105\leq 10^5

  • 1≤1 \leq workers[i] ≤109\leq 10^9

  • 1≤1 \leq tasks.length ≤105\leq 10^5

  • tasks[i].length =2= 2

  • 1≤1 \leq tasks[i][0], tasks[i][1] ≤109\leq 10^9

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Maximize Profit from Task Assignment

Maximize Profit from Task Assignment matches workers to one distinct task each when skill levels exactly meet requirements, with one extra worker able to take any task; return the greatest total profit.

Statement

You are given an integer array workers and a two dimensional integer array tasks, where tasks[i] = [requirement_i, profit_i] indicates that the iextthi^{ ext{th}} task requires an exact skill level of requirement_i and yields a profit of profit_i.

Each worker in workers has a skill level equal to workers[i] and can complete at most 11 task whose skill requirement exactly matches workers[i].

In addition, there is 11 extra worker who can complete any single task without any skill requirement.

Each task can be completed at most once by at most 11 worker.

Return the maximum total profit that can be obtained from completing the tasks.

Constraints:

  • 1≤1 \leq workers.length ≤105\leq 10^5

  • 1≤1 \leq workers[i] ≤109\leq 10^9

  • 1≤1 \leq tasks.length ≤105\leq 10^5

  • tasks[i].length =2= 2

  • 1≤1 \leq tasks[i][0], tasks[i][1] ≤109\leq 10^9