README.md

826. 安排工作以达到最大收益

English Version

题目描述

有一些工作：difficulty[i] 表示第 i 个工作的难度，profit[i] 表示第 i 个工作的收益。

现在我们有一些工人。worker[i] 是第 i 个工人的能力，即该工人只能完成难度小于等于 worker[i] 的工作。

每一个工人都最多只能安排一个工作，但是一个工作可以完成多次。

举个例子，如果 3 个工人都尝试完成一份报酬为 1 的同样工作，那么总收益为 $3。如果一个工人不能完成任何工作，他的收益为 $0 。

我们能得到的最大收益是多少？

 

示例：

输入: difficulty = [2,4,6,8,10], profit = [10,20,30,40,50], worker = [4,5,6,7]
输出: 100 
解释: 工人被分配的工作难度是 [4,4,6,6] ，分别获得 [20,20,30,30] 的收益。

 

提示:

• 1 <= difficulty.length = profit.length <= 10000
• 1 <= worker.length <= 10000
• difficulty[i], profit[i], worker[i]  的范围是 [1, 10^5]

解法

“排序 + 双指针”。

Python3

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

Java

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

C++

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

Go

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
}

...