TNotes.leetcode

Appearance

⏰0826. 安排工作以达到最大收益【中等】

0826. 安排工作以达到最大收益【中等】 ​

1. 📝 题目描述 ​

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

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

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

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

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

示例 1：

txt
输入: 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：

txt
输入: 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 <= 10^4
  • 1 <= difficulty[i], profit[i], worker[i] <= 10^5

2. 🎯 s.1 - 排序 + 双指针 ​

c
int cmpPair(const void* a, const void* b) { return ((int*)a)[0] - ((int*)b)[0]; }
int cmpInt(const void* a, const void* b) { return *(int*)a - *(int*)b; }

int maxProfitAssignment(int* difficulty, int difficultySize, int* profit, int profitSize, int* worker, int workerSize) {
    int n = difficultySize;
    int (*jobs)[2] = malloc(sizeof(int[2]) * n);
    for (int i = 0; i < n; i++) { jobs[i][0] = difficulty[i]; jobs[i][1] = profit[i]; }
    qsort(jobs, n, sizeof(int[2]), cmpPair);
    qsort(worker, workerSize, sizeof(int), cmpInt);
    int res = 0, best = 0, j = 0;
    for (int i = 0; i < workerSize; i++) {
        while (j < n && jobs[j][0] <= worker[i]) {
            if (jobs[j][1] > best) best = jobs[j][1];
            j++;
        }
        res += best;
    }
    free(jobs);
    return res;
}
js
/**
 * @param {number[]} difficulty
 * @param {number[]} profit
 * @param {number[]} worker
 * @return {number}
 */
var maxProfitAssignment = function (difficulty, profit, worker) {
  const jobs = difficulty.map((d, i) => [d, profit[i]])
  jobs.sort((a, b) => a[0] - b[0])
  worker.sort((a, b) => a - b)
  let res = 0,
    best = 0,
    j = 0
  for (const w of worker) {
    while (j < jobs.length && jobs[j][0] <= w) {
      best = Math.max(best, jobs[j][1])
      j++
    }
    res += best
  }
  return res
}
py
class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        jobs = sorted(zip(difficulty, profit))
        worker.sort()
        res = best = j = 0
        for w in worker:
            while j < len(jobs) and jobs[j][0] <= w:
                best = max(best, jobs[j][1])
                j += 1
            res += best
        return res
  • 时间复杂度：O(nlog⁡n+mlog⁡m)，其中 n 是工作数，m 是工人数
  • 空间复杂度：O(n)

算法思路：

  • 将工作按难度排序，工人按能力排序
  • 用双指针维护当前能力范围内的最大收益