发表于 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

• LC 题目链接