What is the main strategy for Most Profit Assigning Work?

Sort jobs by difficulty, compute cumulative max profits, and assign each worker using binary search to find the best job they can perform.

Can a job be assigned to multiple workers?

Yes, a single job can be completed by multiple workers if their abilities meet or exceed the job's difficulty.

What is the time complexity of the optimal solution?

The solution runs in O(n + m + maxAbility) time due to sorting, cumulative max computation, and binary search for each worker.

Why is binary search used in this problem?

Binary search efficiently finds the hardest job a worker can complete, replacing slower linear scans and ensuring maximum profit selection.

What are common mistakes when implementing this solution?

Common errors include not using cumulative max profits, using linear search per worker, and incorrectly restricting jobs to one worker each.

#826

Medium

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

安排工作以达到最大收益

你有 n 个工作和 m 个工人。给定三个数组： difficulty , profit 和 worker ，其中: difficulty[i] 表示第 i 个工作的难度， profit[i] 表示第 i 个工作的收益。 worker[i] 是第 i 个工人的能力，即该工人只能完成难度小于等于 wor…

数组双指针二分查找贪心排序

题目描述

你有 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⁵

lightbulb

解题思路

方法一：排序 + 双指针

我们可以将工作按照能力升序排列，然后将工作按照难度升序排列。

然后我们遍历工人，对于每个工人，我们找出他能完成的工作中收益最大的那个，然后将这个收益加到答案中。

时间复杂度 $O(n \times \log n + m \times \log m)$ ，空间复杂度 $O(n)$ 。其中 $n$ 和 $m$ 分别是数组 profit 和 worker 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def maxProfitAssignment(
        self, difficulty: List[int], profit: List[int], worker: List[int]
    ) -> int:
        worker.sort()
        jobs = sorted(zip(difficulty, profit))
        ans = mx = i = 0
        for w in worker:
            while i < len(jobs) and jobs[i][0] <= w:
                mx = max(mx, jobs[i][1])
                i += 1
            ans += mx
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(n + m + maxAbility) because sorting and cumulative max calculation is linear with respect to the maximum difficulty, and each worker lookup is done via binary search. Space complexity is O(maxAbility) to store the cumulative maximum profits up to each difficulty level.
空间	O(maxAbility)

psychology

面试官常问的追问

外企场景

question_mark
You are expected to optimize for large arrays of workers and jobs.
question_mark
Binary search over difficulty to find suitable jobs is crucial for efficiency.
question_mark
Sorting jobs and precomputing maximum profits indicates correct greedy assignment logic.

warning

常见陷阱

外企场景

error
Assuming each worker must get a unique job instead of allowing repeated job assignments.
error
Forgetting to maintain cumulative maximum profit while iterating sorted jobs.
error
Using linear search per worker instead of binary search, leading to timeouts on large inputs.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Change worker array to allow multiple jobs per worker, requiring dynamic programming.
arrow_right_alt
Limit the number of times a job can be assigned, adding constraint handling.
arrow_right_alt
Replace profit array with profit functions depending on worker skill, increasing algorithmic complexity.

help

常见问题

外企场景

继续练习

#611 有效三角形的个数 #825 适龄的朋友 #786 第 K 个最小的质数分数