Question

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

English Version

题目描述

你有 n 个工作和 m 个工人。给定三个数组： difficulty, profit 和 worker ，其中:

• difficulty[i] 表示第 i 个工作的难度，profit[i] 表示第 i 个工作的收益。
• worker[i] 是第 i 个工人的能力，即该工人只能完成难度小于等于 worker[i] 的工作。

每个工人 最多 只能安排 一个 工作，但是一个工作可以 完成多次 。

• 举个例子，如果 3 个工人都尝试完成一份报酬为 $1 的同样工作，那么总收益为 $3 。如果一个工人不能完成任何工作，他的收益为 $0 。

返回 _在把工人分配到工作岗位后，我们所能获得的最大利润 _。

 

示例 1：

输入: difficulty = [2,4,6,8,10], profit = [10,20,30,40,50], worker = [4,5,6,7]
输出: 100 
解释: 工人被分配的工作难度是 [4,4,6,6] ，分别获得 [20,20,30,30] 的收益。

示例 2:

输入: difficulty = [85,47,57], profit = [24,66,99], worker = [40,25,25]
输出: 0

 

提示:

• n == difficulty.length
• n == profit.length
• m == worker.length
• 1 <= n, m <= 104
• 1 <= difficulty[i], profit[i], worker[i] <= 105

解法

方法一

class Solution:
  def maxProfitAssignment(
    self, difficulty: List[int], profit: List[int], worker: List[int]
  ) -> int:
    n = len(difficulty)
    job = [(difficulty[i], profit[i]) for i in range(n)]
    job.sort(key=lambda x: x[0])
    worker.sort()
    i = t = res = 0
    for w in worker:
      while i < n and job[i][0] <= w:
        t = max(t, job[i][1])
        i += 1
      res += t
    return res

class Solution {
  public int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
    int n = difficulty.length;
    List<int[]> job = new ArrayList<>();
    for (int i = 0; i < n; ++i) {
      job.add(new int[] {difficulty[i], profit[i]});
    }
    job.sort(Comparator.comparing(a -> a[0]));
    Arrays.sort(worker);
    int res = 0;
    int i = 0, t = 0;
    for (int w : worker) {
      while (i < n && job.get(i)[0] <= w) {
        t = Math.max(t, job.get(i++)[1]);
      }
      res += t;
    }
    return res;
  }
}

class Solution {
public:
  int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {
    int n = difficulty.size();
    vector<pair<int, int>> job;
    for (int i = 0; i < n; ++i) {
      job.push_back({difficulty[i], profit[i]});
    }
    sort(job.begin(), job.end());
    sort(worker.begin(), worker.end());
    int i = 0, t = 0;
    int res = 0;
    for (auto w : worker) {
      while (i < n && job[i].first <= w) {
        t = max(t, job[i++].second);
      }
      res += t;
    }
    return res;
  }
};

func maxProfitAssignment(difficulty []int, profit []int, worker []int) int {
  var job [][2]int
  for i := range difficulty {
    job = append(job, [2]int{difficulty[i], profit[i]})
  }

  sort.SliceStable(job, func(i, j int) bool { return job[i][0] <= job[j][0] })
  sort.Ints(worker)
  i, t, n, res := 0, 0, len(difficulty), 0
  for _, w := range worker {
    for i < n && job[i][0] <= w {
      t = max(t, job[i][1])
      i++
    }
    res += t
  }
  return res
}