Welcome to Subscribe On Youtube
826. Most Profit Assigning Work
Description
You have n
jobs and m
workers. You are given three arrays: difficulty
, profit
, and worker
where:
difficulty[i]
andprofit[i]
are the difficulty and the profit of thei^{th}
job, andworker[j]
is the ability ofj^{th}
worker (i.e., thej^{th}
worker can only complete a job with difficulty at mostworker[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

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; } }

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; } };

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

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 }