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 i
th job, and profit[i]
is the profit of the i
th job.
Now we have some workers. worker[i]
is the ability of the i
th 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 }