Leetcode826-安排工作以达到最大收益
①把difficultly和profit合并为一个数组task，然后按difficultly升序，profit降序对task进行排序。
②遍历task，每个任务所能获得的最大利润为所有小于等于这个任务难度的任务的最大利润，用前缀和的思想来处理即可。
③对于每个工人，二分查找task中难度不大于这个工人能力的最大难度的任务，所对应的利润即为这个工人能获得的最大利润。
class Solution {
public:int maxProfitAssignment(vector& difficulty, vector& profit, vector& worker) {int n=profit.size();vector> task(n);for(int i=0;ib.second;else return a.firstfirst>c) p--;ans+=p->second;}return ans;}
}; 时间复杂度：O（nlogn+wlogn），n为任务数量，w为工人数量
空间复杂度：O（n）
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！