1748. Assign Crews by Skill
A staffing agency has contract jobs and available workers. Job j needs a worker whose skill is at least difficulty[j] and pays profit[j]. Worker w has skill level skill[w]. Every worker takes on at most one job, and every job can be given to at most one worker; jobs nobody takes pay nothing and workers may stay unassigned.
Return the maximum total profit the agency can collect, as a long. Sort the jobs by difficulty and the workers by skill, sweep the workers from weakest to strongest while pushing every job that the current worker can do into a max-heap of profits, and give the worker the best job in the heap if there is one. This runs in O((n + m) log (n + m)) time with O(n + m) extra space.
Example 1
- Input:
- difficulty = [2,5,3], profit = [10,50,30], skill = [3,6]
- Output:
- 80
- Explanation:
The skill-3 worker can only do the jobs paying 10 and 30, so they take 30; the skill-6 worker takes the 50 job, for 80.
Example 2
- Input:
- difficulty = [1,1,1], profit = [5,6,7], skill = [10]
- Output:
- 7
- Explanation:
There is a single worker, who takes the best-paying job, 7.
Example 3
- Input:
- difficulty = [4], profit = [9], skill = [1,2,3]
- Output:
- 0
- Explanation:
No worker has skill 4, so the only job stays undone and the profit is 0.
Constraints
1 ≤ n ≤ 105 (n = difficulty.length = profit.length)
1 ≤ skill.length ≤ 105
1 ≤ difficulty[j], profit[j], skill[w] ≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 4,000 msC++ 1,000 msJava 2,000 msJavaScript 2,000 msTypeScript 2,000 ms
Expected complexity
- Time
- O((n + m) log (n + m))
- Space
- O(n + m)