Medium

题目描述

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

  • difficulty[i] 和 profit[i] 分别是第 i 个工作的难度和收益
  • worker[j] 是第 j 个工人的能力（即第 j 个工人只能完成难度最多为 worker[j] 的工作）

每个工人最多只能分配一个工作，但一个工作可以完成多次。

  • 例如，如果三个工人尝试同一个报酬为 $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 <= 10^4
  • 1 <= difficulty[i], profit[i], worker[j] <= 10^5

解题思路

这道题的核心思想是为每个工人找到他能完成的工作中收益最大的那个。

基本思路：

  1. 将工作按难度排序，同时记录对应的收益
  2. 预处理：对于每个难度级别，计算到该难度为止能获得的最大收益
  3. 对每个工人，使用二分查找找到他能完成的最大难度工作，获取对应的最大收益

详细分析：

  • 首先将工作和收益配对并按难度排序
  • 然后遍历排序后的工作，维护一个单调递增的最大收益数组。这样对于任意难度d，我们可以O(1)时间知道难度不超过d的工作的最大收益
  • 对每个工人使用二分查找找到他能胜任的最大难度工作
  • 累加所有工人的最大收益

时间复杂度优化： 还可以使用双指针方法，将工人也排序后用双指针遍历，时间复杂度相同但常数更小。这里给出二分查找的解法，更容易理解且适用性更广。

代码实现

class Solution {
public:
    int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {
        int n = difficulty.size();
        vector<pair<int, int>> jobs;
        
        // 将工作按难度和收益配对
        for (int i = 0; i < n; i++) {
            jobs.push_back({difficulty[i], profit[i]});
        }
        
        // 按难度排序
        sort(jobs.begin(), jobs.end());
        
        // 预处理：计算到每个难度为止的最大收益
        for (int i = 1; i < n; i++) {
            jobs[i].second = max(jobs[i].second, jobs[i-1].second);
        }
        
        int totalProfit = 0;
        for (int ability : worker) {
            // 二分查找最大能完成的工作
            int left = 0, right = n - 1, maxProfit = 0;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (jobs[mid].first <= ability) {
                    maxProfit = jobs[mid].second;
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            totalProfit += maxProfit;
        }
        
        return totalProfit;
    }
};

class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        # 将工作按难度和收益配对并排序
        jobs = sorted(zip(difficulty, profit))
        
        # 预处理：计算到每个难度为止的最大收益
        for i in range(1, len(jobs)):
            jobs[i] = (jobs[i][0], max(jobs[i][1], jobs[i-1][1]))
        
        total_profit = 0
        for ability in worker:
            # 二分查找最大能完成的工作
            left, right = 0, len(jobs) - 1
            max_profit = 0
            while left <= right:
                mid = (left + right) // 2
                if jobs[mid][0] <= ability:
                    max_profit = jobs[mid][1]
                    left = mid + 1
                else:
                    right = mid - 1
            total_profit += max_profit
        
        return total_profit

public class Solution {
    public int MaxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
        int n = difficulty.Length;
        var jobs = new List<(int difficulty, int profit)>();
        
        // 将工作按难度和收益配对
        for (int i = 0; i < n; i++) {
            jobs.Add((difficulty[i], profit[i]));
        }
        
        // 按难度排序
        jobs.Sort((a, b) => a.difficulty.CompareTo(b.difficulty));
        
        // 预处理：计算到每个难度为止的最大收益
        for (int i = 1; i < n; i++) {
            jobs[i] = (jobs[i].difficulty, Math.Max(jobs[i].profit, jobs[i-1].profit));
        }
        
        int totalProfit = 0;
        foreach (int ability in worker) {
            // 二分查找最大能完成的工作
            int left = 0, right = n - 1, maxProfit = 0;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (jobs[mid].difficulty <= ability) {
                    maxProfit = jobs[mid].profit;
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            totalProfit += maxProfit;
        }
        
        return totalProfit;
    }
}

var maxProfitAssignment = function(difficulty, profit, worker) {
    const n = difficulty.length;
    const jobs = [];
    
    // 将工作按难度和收益配对
    for (let i = 0; i < n; i++) {
        jobs.push([difficulty[i], profit[i]]);
    }
    
    // 按难度排序
    jobs.sort((a, b) => a[0] - b[0]);
    
    // 预处理：计算到每个难度为止的最大收益
    for (let i = 1; i < n; i++) {
        jobs[i][1] = Math.max(jobs[i][1], jobs[i-1][1]);
    }
    
    let totalProfit = 0;
    for (const ability of worker) {
        // 二分查找最大能完成的工作
        let left = 0, right = n - 1, maxProfit = 0;
        while (left <= right) {
            const mid = Math.floor((left + right) / 2);
            if (jobs[mid][0] <= ability) {
                maxProfit = jobs[mid][1];
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        totalProfit += maxProfit;
    }
    
    return totalProfit;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

操作时间复杂度空间复杂度
排序工作O(n log n)O(n)
预处理最大收益O(n)O(1)
二分查找所有工人O(m log n)O(1)
总计O(n log n + m log n)O(n)

其中 n 为工作数量，m 为工人数量。

相关题目