leetcode 826. Most Profit Assigning Work 安排工作以达到最大收益

Problem: 826. Most Profit Assigning Work 安排工作以达到最大收益

解题过程

首先按照相同方式排序difficulty和profit，首先difficulty和索引放到一起排序，然后将profit的数值放到对应的地方，就相当按照difficulty排序的方式排序了profit，最后单独排序difficulty，对每个worker，二分查找上界最大值，对上界下面的拿到最大利润，累加即可的

Code

class Solution { public: int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) { vector<pair<int, int>> tr; int n = difficulty.size(), m = worker.size(); for(int i = 0; i < n; i++) { tr.push_back({difficulty[i], i}); } function<bool(pair<int, int>&, pair<int, int>&)> fun = [&](pair<int, int>& a, pair<int, int>& c) { return a.first < c.first; }; sort(tr.begin(), tr.end(), fun); sort(difficulty.begin(), difficulty.end()); vector<int> profitCP = profit; for(int i = 0; i < n; i++) { profitCP[i] = profit[tr[i].second]; } int ind, sum = 0; for(int i = 0; i < m; i++) { ind = upper_bound(difficulty.begin(), difficulty.end(), worker[i]) - difficulty.begin(); if(ind > 0) { sum += *max_element(profitCP.begin(), profitCP.begin() + ind); } } return sum; } };

官方题解的

class Solution { public: int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) { vector<pair<int, int>> tr; int n = difficulty.size(), m = worker.size(); for(int i = 0; i < n; i++) { tr.push_back({difficulty[i], profit[i]}); } function<bool(pair<int, int>&, pair<int, int>&)> fun = [&](pair<int, int>& a, pair<int, int>& c) { return a.first < c.first; }; sort(tr.begin(), tr.end(), fun); sort(worker.begin(), worker.end()); // sort(difficulty.begin(), difficulty.end()); // vector<int> profitCP = profit; // for(int i = 0; i < n; i++) { // profitCP[i] = profit[tr[i].second]; // } int ind, sum = 0, best = 0; int j = 0; for(int i = 0; i < m; i++) { while(j < n && tr[j].first <= worker[i]) { best = max(best, tr[j].second); j++; } sum += best; // ind = upper_bound(difficulty.begin(), difficulty.end(), worker[i]) - difficulty.begin(); // if(ind > 0) { // sum += *max_element(profitCP.begin(), profitCP.begin() + ind); // } } return sum; } };