安排工作以达到最大收益 图解题解

这道题到底在问什么

输入

difficulty=[2,4,6,8,10], profit=[10,20,30,40,50], worker=[4,5,6,7]

输出

100

最优解：一步一步想明白

1. 3记住「按难度排序工作、按能力排序工人;指针不回退地纳入难度够到的工作、维护最大收益 best,每个工人取 best」,下面每帧都在套它。
2. 4先排序。工作按难度排好:难度 [2, 4, 6, 8, 10]、对应收益 [10, 20, 30, 40, 50](右边面板就是这张「难度→收益」对照表);工人按能力排好 [4, 5, 6, 7]。排序是双指针不回退的前提。
3. 5来了个能力 4 的工人。他能做难度不超过 4 的任意工作,目标是从这些工作里挑收益最高的。指针从上一个工人停下的位置接着往右扫,不回退。
4. 6难度 2 不超过 4,这份工作他做得了,纳入候选。它的收益是 10,比之前的 best 高,best 更新成 10。注意 best 只增不减,后面工人能力更强、能用的工作只多不少。
5. 7难度 4 不超过 4,这份工作他做得了,纳入候选。它的收益是 20,比之前的 best 高,best 更新成 20。注意 best 只增不减,后面工人能力更强、能用的工作只多不少。
6. 8再往右,难度 6 已经大于 4,这个工人做不了,停。指针就停在这里,等下一个能力更强的工人接着往右走。
7. 9这个工人就拿他能力内的最高收益 20,加进总收益,现在 ans = 20。他不一定做难度最高那份,而是做收益最高那份,这正是要维护 best 的原因。
8. 10来了个能力 5 的工人。他能做难度不超过 5 的任意工作,目标是从这些工作里挑收益最高的。指针从上一个工人停下的位置接着往右扫,不回退。
9. 11再往右,难度 6 已经大于 5,这个工人做不了,停。指针就停在这里,等下一个能力更强的工人接着往右走。
10. 12这个工人就拿他能力内的最高收益 20,加进总收益,现在 ans = 40。他不一定做难度最高那份,而是做收益最高那份,这正是要维护 best 的原因。
11. 13来了个能力 6 的工人。他能做难度不超过 6 的任意工作,目标是从这些工作里挑收益最高的。指针从上一个工人停下的位置接着往右扫,不回退。
12. 14难度 6 不超过 6,这份工作他做得了,纳入候选。它的收益是 30,比之前的 best 高,best 更新成 30。注意 best 只增不减,后面工人能力更强、能用的工作只多不少。
13. 15再往右,难度 8 已经大于 6,这个工人做不了,停。指针就停在这里,等下一个能力更强的工人接着往右走。
14. 16这个工人就拿他能力内的最高收益 30,加进总收益,现在 ans = 70。他不一定做难度最高那份,而是做收益最高那份,这正是要维护 best 的原因。
15. 17来了个能力 7 的工人。他能做难度不超过 7 的任意工作,目标是从这些工作里挑收益最高的。指针从上一个工人停下的位置接着往右扫,不回退。
16. 18再往右,难度 8 已经大于 7,这个工人做不了,停。指针就停在这里,等下一个能力更强的工人接着往右走。
17. 19这个工人就拿他能力内的最高收益 30,加进总收益,现在 ans = 100。他不一定做难度最高那份,而是做收益最高那份,这正是要维护 best 的原因。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from typing import List
class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        jobs = sorted(zip(difficulty, profit))
        worker.sort()
        ans = best = i = 0
        for w in worker:
            while i < len(jobs) and jobs[i][0] <= w:
                best = max(best, jobs[i][1])
                i += 1
            ans += best
        return ans

#include <algorithm>
#include <vector>
using namespace std;
class Solution {
public:
    int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {
        vector<pair<int,int>> jobs;
        for (int i = 0; i < (int)difficulty.size(); ++i) jobs.push_back({difficulty[i], profit[i]});
        sort(jobs.begin(), jobs.end());
        sort(worker.begin(), worker.end());
        int ans = 0, best = 0, i = 0;
        for (int w : worker) {
            while (i < (int)jobs.size() && jobs[i].first <= w) best = max(best, jobs[i++].second);
            ans += best;
        }
        return ans;
    }
};

import java.util.*;
class Solution {
    public int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
        int n = difficulty.length;
        int[][] jobs = new int[n][2];
        for (int i = 0; i < n; i++) { jobs[i][0] = difficulty[i]; jobs[i][1] = profit[i]; }
        Arrays.sort(jobs, Comparator.comparingInt(a -> a[0]));
        Arrays.sort(worker);
        int ans = 0, best = 0, i = 0;
        for (int w : worker) {
            while (i < n && jobs[i][0] <= w) best = Math.max(best, jobs[i++][1]);
            ans += best;
        }
        return ans;
    }
}

复杂度

面试官可能追问