JZX轻语：简
LeetCode 826 - 安排工作以达到最大收益
发表于2024年05月12日
朴素做法是，对于每一个worker，遍历所有的工作，找到难度满足工人能力中收益的最大值，这样的复杂度为O(nm)。可以通过排序的方法降到O(nlogn + mlogm)：对工作按工作难度进行排序，以及对工人的能力进行排序，使用一个指针cur_valid_work_cnt维护当前有效的工作数量(即对于当前遍历的工人都能干的活)，并使用cur_valid_work_max_profit维护当前有效工作最大收益，然后对于每一个worker，首先更新下有效工作信息(cur_valid_work_cnt指针往右移动直到下一个工作不满足工人难度，并最大收益)，并累加有效工作的最大收益即可。
class Solution:
def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
works = sorted(zip(difficulty, profit))
worker.sort()
ans = 0
cur_valid_work_cnt = 0
cur_valid_work_max_profit = 0
for i, cap in enumerate(worker):
while cur_valid_work_cnt < len(works) and works[cur_valid_work_cnt][0] <= cap:
cur_valid_work_max_profit = max(cur_valid_work_max_profit, works[cur_valid_work_cnt][1])
cur_valid_work_cnt += 1
ans += cur_valid_work_max_profit
return ans