安排工作以达到最大收益

难度: Medium

你有 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 <= 10⁴
1 <= difficulty[i], profit[i], worker[i] <= 10⁵

Submission

运行时间: 66 ms

内存: 18.5 MB

class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        s = sorted(zip(profit,difficulty),reverse = True)
        l = len(s)
        worker.sort(reverse = True)
        i = 0
        res = 0
        for ability in worker:
            while i < l and ability < s[i][1]:i += 1
            if i == l:break
            res += s[i][0]
        return res

Explain

题解首先将工作按照利润进行降序排序，如果利润相同则按难度升序排序。随后将工人能力也进行降序排序。使用贪心算法，从能力最强的工人开始，为每个工人分配他能够完成的利润最大的工作。这是通过一个指针i来维持当前能分配的最大利润的工作。如果工人的能力不足以完成当前i指向的工作，则i向后移动，直到找到该工人能完成的工作。这样可以确保每个工人都尽可能地获取最大利润。

时间复杂度: O(n log n + m log m)

空间复杂度: O(1)

class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        # 将工作按利润降序排序，如果利润相同按难度排序
        s = sorted(zip(profit, difficulty), reverse=True)
        l = len(s)  # 工作数量
        # 对工人的能力进行降序排序
        worker.sort(reverse=True)
        i = 0  # 用于遍历工作的指针
        res = 0  # 初始化总利润
        # 遍历每个工人的能力
        for ability in worker:
            # 寻找该工人能完成的最高利润工作
            while i < l and ability < s[i][1]:
                i += 1
            # 如果所有工作都不能由当前工人完成，停止分配
            if i == l: break
            # 为工人分配工作，并累加利润
            res += s[i][0]
        return res

Explore

在利润相同的情况下，按难度升序排序可以最大化工人的工作机会。这样做确保了在面对相同利润的多个工作时，优先选择难度较低的工作。这样，更多的工人（包括那些能力较低的工人）可以完成这些工作，从而增加整体的利润累积。

将工人能力进行降序排序的原因是为了尽可能地让能力最强的工人先选择工作，这样能够最大化利用工人的潜力。这种排序方式确保了能力最强的工人可以首先挑选他们能够完成的最高利润工作，由于他们的能力较高，选择的范围也更广，因此可以最大化每次的利润选择。这种策略帮助实现最大利润，因为它优先考虑了最大化每个工作分配的收益。

贪心策略在这种特定情况下通常能找到最大利润，因为它总是优先分配可能获得的最大利润。然而，贪心策略的局限性在于它可能不考虑全局最优解，只关注当前的局部最优解。在某些复杂情况下，如果工作与工人的匹配存在多种组合，且这些组合之间相互影响，则单纯的贪心策略可能无法获得全局最优解。

这种处理方式实际上不会导致后续有能力较低的工人错过可完成的工作。因为算法已经将工人按能力进行了降序排序，所以如果一个能力较高的工人都无法完成当前的工作，那么能力更低的工人同样无法完成这些工作。因此，这种处理只是提前终止了无用的迭代，而不会影响结果的正确性。