LC826. 安排工作以达到最大收益

原题链接
image.png

思路

  • 将工作按照难度进行排序。难度越大不一定收益就越多，但是可以在预处理（左边最大值辅助数组）之后，在O(1)时间内得知，满足条件的区间里面最大的收益值是多少。
  • 所谓预处理，就是建立一个left_max数组，该数组记录了出现在左边的最大值，left_max[i]表示从第0个位置，到第i个位置，出现的最大的数值。
  • 对于工人i而言，可以通过二分查找，在LC826. 安排工作以达到最大收益 - 图2时间内找到difficulty值不大于worker[i]的区间的右端点，该端点记为x，那么这个工人能取得的最大收益就是left_max[x]。
  • left_max数组预处理，left_max[i]表示从0到i的最大数字 ```cpp vector left_max(n, 0); left_max[0] = pp[0].second;

for (int i = 1; i < n; i++) { left_max[i] = max(left_max[i - 1], pp[i].second); }

  2. - 二分查找，找左侧区间的右端点
  3. ```cpp
  4. while (left < right) {
  5.     int mid = (left + right + 1) / 2;
  6.     if (pp[mid].first <= num) {
  7.         left = mid;
  8.     } else {
  9.         right = mid - 1;
  10.     }
  11. }

代码

class Solution {
public:
    int findEnd(int num, vector<pair<int,int>>& pp) {
        int n = pp.size();
        int left = 0, right = n - 1;
        while (left < right) {
            int mid = (left + right + 1) / 2;
            if (pp[mid].first <= num) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }

        if (pp[right].first <= num) {
            return right;
        } else {
            return -1;
        }
    }

    static bool cmp(const pair<int, int> p1, const pair<int, int> p2) {
        return p1.first < p2.first;
    }
    int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {
        int n = difficulty.size();
        vector<pair<int, int>> pp(n, {0, 0});
        for (int i = 0; i < n; i++) {
            pp[i].first = difficulty[i];
            pp[i].second = profit[i];
        }

        sort(pp.begin(), pp.end(), cmp);
        // 对于每个满足条件的条件，计算左边开始的最大收益值
        vector<int> left_max(n, 0);
        left_max[0] = pp[0].second;
        for (int i = 1; i < n; i++) {
            left_max[i] = max(left_max[i - 1], pp[i].second);
        }

        int cnt = 0;
        // 找到满足工人能力条件的区间的右端点，然后计算这个区间曾经出现过的最大值即可
        int worker_num = worker.size();
        for (int i = 0; i < worker_num; i++) {
            int right_end = findEnd(worker[i], pp);
            if (right_end == -1) {
                continue;
            } else {
                cnt += left_max[right_end];
            }
        }

        return cnt;
    }
};