#826
Most Profit Assigning Work
specialist · 775 · lc medium +31 · verified · 56.1% accepted · 2,535 likes · top 50%
Description
You have n jobs and m workers, described by three arrays difficulty, profit, and worker:
- difficulty[i] and profit[i] are the difficulty and profit of job i.
- worker[j] is the maximum job difficulty worker j can handle.
Each worker is assigned at most one job, but a single job may be performed by multiple workers.
- For example, if three workers each complete a job paying $1, the combined profit is $3. A worker assigned no job earns $0.
Return the maximum total profit achievable by optimally assigning workers to 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
Code
1
2
3