Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/826.html

826. Most Profit Assigning Work (Medium)

We have jobs: difficulty[i] is the difficulty of the ith job, and profit[i] is the profit of the ith job. 

Now we have some workers. worker[i] is the ability of the ith worker, which means that this worker can only complete a job with difficulty at most worker[i]

Every worker can be assigned at most one job, but one job can be completed multiple times.

For example, if 3 people attempt the same job that pays $1, then the total profit will be $3.  If a worker cannot complete any job, his profit is $0.

What is the most profit we can make?

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 profit of [20,20,30,30] seperately.

Notes:

  • 1 <= difficulty.length = profit.length <= 10000
  • 1 <= worker.length <= 10000
  • difficulty[i], profit[i], worker[i]  are in range [1, 10^5]

Companies:
Nutanix

Related Topics:
Two Pointers

Solution 1.

  • class Solution {
        public int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
            int jobs = difficulty.length;
            int[][] difficultyProfit = new int[jobs][2];
            for (int i = 0; i < jobs; i++) {
                difficultyProfit[i][0] = difficulty[i];
                difficultyProfit[i][1] = profit[i];
            }
            Arrays.sort(difficultyProfit, new Comparator<int[]>() {
                public int compare(int[] difficultyProfit1, int[] difficultyProfit2) {
                    if (difficultyProfit1[0] != difficultyProfit2[0])
                        return difficultyProfit1[0] - difficultyProfit2[0];
                    else
                        return difficultyProfit2[1] - difficultyProfit1[1];
                }
            });
            for (int i = 1; i < jobs; i++)
                difficultyProfit[i][1] = Math.max(difficultyProfit[i - 1][1], difficultyProfit[i][1]);
            int totalProfit = 0;
            for (int ability : worker) {
                int maxProfit = binarySearch(difficultyProfit, ability);
                totalProfit += maxProfit;
            }
            return totalProfit;
        }
    
        public int binarySearch(int[][] difficultyProfit, int ability) {
            int low = 0, high = difficultyProfit.length - 1;
            int index = -1;
            while (low <= high) {
                int mid = (high - low) / 2 + low;
                int difficulty = difficultyProfit[mid][0];
                if (difficulty == ability) {
                    index = mid;
                    break;
                } else if (difficulty > ability)
                    high = mid - 1;
                else
                    low = mid + 1;
            }
            if (index < 0)
                index = low - 1;
            if (index < 0)
                return 0;
            else
                return difficultyProfit[index][1];
        }
    }
    
    ############
    
    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;
        }
    }
    
  • // OJ: https://leetcode.com/problems/most-profit-assigning-work/
    // Time: O(NlogN)
    // Space: O(N)
    class Solution {
    public:
        int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {
            map<int, int, greater<int>> diffToProfit;
            int N = difficulty.size(), maxProfit = 0, ans = 0;
            for (int i = 0; i < N; ++i) {
                diffToProfit[difficulty[i]] = max(diffToProfit[difficulty[i]], profit[i]);
            }
            for (auto it = diffToProfit.rbegin(); it != diffToProfit.rend(); ++it) {
                it->second = maxProfit = max(maxProfit, it->second);
            }
            for (int w : worker) {
                auto it = diffToProfit.lower_bound(w);
                if (it != diffToProfit.end()) ans += it->second;
            }
            return ans;
        }
    };
    
  • 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
    
    ############
    
    class Solution(object):
        def maxProfitAssignment(self, difficulty, profit, worker):
            """
            :type difficulty: List[int]
            :type profit: List[int]
            :type worker: List[int]
            :rtype: int
            """
            jobs = sorted([a, b] for a, b in zip(difficulty, profit))
            curMax, i = 0, 0
            res = 0
            for w in sorted(worker):
                while i < len(jobs) and w >= jobs[i][0]:
                    curMax = max(curMax, jobs[i][1])
                    i += 1
                res += curMax
            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
    }
    
    func max(a, b int) int {
    	if a > b {
    		return a
    	}
    	return b
    }
    

All Problems

All Solutions