[每日一题] 826.安排工作以达到最大收益

博主： Richard
发布时间：2024 年 05 月 17 日
83 次浏览
暂无评论
862字数
分类： LeetCode

> https://leetcode.cn/problems/most-profit-assigning-work/description/?envType=daily-question&envId=2024-05-02

这道题思路比较好想。工人可以做相同的工作，所以每个工人选择能力范围内收益最大的工作即可。

可以将工作按收益排序，每个工人从大到小遍历所有工作，找到难度小于自身能力的工作即可。

对工人也可以按照能力排序，从高往低遍历，因为能力低的工人获得的收益一定小于等于能力高的工人，可以节省时间。

```c++
class Solution {
public:
    int maxProfitAssignment(std::vector<int> &difficulty, std::vector<int> &profit, std::vector<int> &worker) {
        const int n = profit.size();

std::vector<int> index(n);
        std::iota(index.begin(), index.end(), 0);
        std::sort(index.begin(), index.end(), [&](const int &a, const int &b) { return profit[a] > profit[b]; });
        std::sort(worker.begin(), worker.end(), std::greater<int>());

int res = 0, begin = 0;
        for (auto &ability: worker) {
            for (int i = begin; i < n; i++) {
                if (difficulty[index[i]] <= ability) {
                    res += profit[index[i]];
                    begin = i;
                    break;
                }
            }
        }

return res;
    }
};
```

- 时间复杂度：$O(nlogn + mlogm)$ ，其中 $n$ 为工作的数量， $m$ 为工人的数量。
- 空间复杂度：$O(n + m)$ 。

最后修改：2024 年 05 月 17 日