0826-安排工作以达到最大收益

你有 n 个工作和 m 个工人。给定三个数组： difficulty, profit 和 worker ，其中:

• difficulty[i] 表示第 i 个工作的难度，profit[i] 表示第 i 个工作的收益。
• worker[i] 是第 i 个工人的能力，即该工人只能完成难度小于等于 worker[i] 的工作。

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

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

返回 _在把工人分配到工作岗位后，我们所能获得的最大利润 _。

示例 1：

**输入:** 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] 的收益。

示例 2:

**输入:** difficulty = [85,47,57], profit = [24,66,99], worker = [40,25,25]
**输出:** 0

提示:

• n == difficulty.length
• n == profit.length
• m == worker.length
• 1 <= n, m <= 104
• 1 <= difficulty[i], profit[i], worker[i] <= 105

方法：排序

想法

我们可以以任意顺序考虑工人，所以我们按照能力大小排序。

如果我们先访问低难度的工作，那么收益一定是截至目前最好的。

算法

我们使用 “双指针” 的方法去安排任务。我们记录最大可用利润 best。对于每个能力值为 skill 的工人，找到难度小于等于能力值的任务，并将如结果中。

[]

import java.awt.Point;

class Solution {
    public int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
        int N = difficulty.length;
        Point[] jobs = new Point[N];
        for (int i = 0; i < N; ++i)
            jobs[i] = new Point(difficulty[i], profit[i]);
        Arrays.sort(jobs, (a, b) -> a.x - b.x);
        Arrays.sort(worker);

        int ans = 0, i = 0, best = 0;
        for (int skill: worker) {
            while (i < N && skill >= jobs[i].x)
                best = Math.max(best, jobs[i++].y);
            ans += best;
        }

        return ans;
    }
}

[]

class Solution(object):
    def maxProfitAssignment(self, difficulty, profit, worker):
        jobs = zip(difficulty, profit)
        jobs.sort()
        ans = i = best = 0
        for skill in sorted(worker):
            while i < len(jobs) and skill >= jobs[i][0]:
                best = max(best, jobs[i][1])
                i += 1
            ans += best
        return ans

复杂度分析

• 时间复杂度：O(N \log N + Q \log Q)，其中 N 是任务个数，Q 是工人数量。
• 空间复杂度：O(N)，jobs 的额外空间。