Description#
You have n
jobs and m
workers. You are given three arrays: difficulty
, profit
, and worker
where:
difficulty[i]
and profit[i]
are the difficulty and the profit of the i^{th}
job, andworker[j]
is the ability of j^{th}
worker (i.e., the j^{th}
worker can only complete a job with difficulty at most worker[j]
).
Every worker can be assigned at most one job, but one job can be completed multiple times.
 For example, if three workers attempt the same job that pays
$1
, then the total profit will be $3
. If a worker cannot complete any job, their profit is $0
.
Return the maximum profit we can achieve after assigning the workers to the 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
Constraints:
n == difficulty.length
n == profit.length
m == worker.length
1 <= n, m <= 10^{4}
1 <= difficulty[i], profit[i], worker[i] <= 10^{5}
Solutions#
Solution 1#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 class Solution:
def maxProfitAssignment(
self, difficulty: List[int], profit: List[int], worker: List[int]
) > int:
n = len(difficulty)
job = [(difficulty[i], profit[i]) for i in range(n)]
job.sort(key=lambda x: x[0])
worker.sort()
i = t = res = 0
for w in worker:
while i < n and job[i][0] <= w:
t = max(t, job[i][1])
i += 1
res += t
return res

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 class Solution {
public int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
int n = difficulty.length;
List<int[]> job = new ArrayList<>();
for (int i = 0; i < n; ++i) {
job.add(new int[] {difficulty[i], profit[i]});
}
job.sort(Comparator.comparing(a > a[0]));
Arrays.sort(worker);
int res = 0;
int i = 0, t = 0;
for (int w : worker) {
while (i < n && job.get(i)[0] <= w) {
t = Math.max(t, job.get(i++)[1]);
}
res += t;
}
return res;
}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 class Solution {
public:
int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {
int n = difficulty.size();
vector<pair<int, int>> job;
for (int i = 0; i < n; ++i) {
job.push_back({difficulty[i], profit[i]});
}
sort(job.begin(), job.end());
sort(worker.begin(), worker.end());
int i = 0, t = 0;
int res = 0;
for (auto w : worker) {
while (i < n && job[i].first <= w) {
t = max(t, job[i++].second);
}
res += t;
}
return res;
}
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 func maxProfitAssignment(difficulty []int, profit []int, worker []int) int {
var job [][2]int
for i := range difficulty {
job = append(job, [2]int{difficulty[i], profit[i]})
}
sort.SliceStable(job, func(i, j int) bool { return job[i][0] <= job[j][0] })
sort.Ints(worker)
i, t, n, res := 0, 0, len(difficulty), 0
for _, w := range worker {
for i < n && job[i][0] <= w {
t = max(t, job[i][1])
i++
}
res += t
}
return res
}
