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] and profit[i] are the difficulty and the profit of the ith job, and
  • worker[j] is the ability of jth worker (i.e., the jth 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 <= 104
  • 1 <= difficulty[i], profit[i], worker[i] <= 105

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
    }
    
  • function maxProfitAssignment(difficulty: number[], profit: number[], worker: number[]): number {
        const n = profit.length;
        worker.sort((a, b) => a - b);
        const jobs = Array.from({ length: n }, (_, i) => [difficulty[i], profit[i]]);
        jobs.sort((a, b) => a[0] - b[0]);
        let [ans, mx, i] = [0, 0, 0];
        for (const w of worker) {
            while (i < n && jobs[i][0] <= w) {
                mx = Math.max(mx, jobs[i++][1]);
            }
            ans += mx;
        }
        return ans;
    }
    
    

All Problems

All Solutions