How can I solve the Maximum Number of Tasks You Can Assign problem using binary search?

Start by sorting the tasks and workers. Then, apply binary search over the number of tasks that can be completed, checking feasibility at each step by allocating tasks greedily.

What is the key to optimizing the task allocation in this problem?

The key is to first assign tasks without pills, then use the pills optimally on workers who need a boost to meet task requirements.

How do I manage the pill distribution in this problem?

Pills should be distributed to the weakest workers who are closest to completing their assigned tasks without help, maximizing the number of tasks that can be completed.

What are the time and space complexity of the solution for Maximum Number of Tasks You Can Assign?

The time complexity is O(n log n + m log m + min(m, n) log^2 min(m, n)) and the space complexity is O(log n + log m + min(m, n)).

How does sorting help in solving the Maximum Number of Tasks You Can Assign?

Sorting the tasks and workers helps by allowing a greedy approach to assign tasks in increasing order of difficulty and worker strength, ensuring optimal allocation with pills.

#2071

Hard

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

LeetCode 题解工作台

你可以安排的最多任务数目

给你 n 个任务和 m 个工人。每个任务需要一定的力量值才能完成，需要的力量值保存在下标从 0 开始的整数数组 tasks 中，第 i 个任务需要 tasks[i] 的力量才能完成。每个工人的力量值保存在下标从 0 开始的整数数组 workers 中，第 j 个工人的力量值为 workers[j] …

数组双指针二分查找贪心队列

题目描述

给你 n 个任务和 m 个工人。每个任务需要一定的力量值才能完成，需要的力量值保存在下标从 0 开始的整数数组 tasks 中，第 i 个任务需要 tasks[i] 的力量才能完成。每个工人的力量值保存在下标从 0 开始的整数数组 workers 中，第 j 个工人的力量值为 workers[j] 。每个工人只能完成一个任务，且力量值需要 大于等于 该任务的力量要求值（即 workers[j] >= tasks[i] ）。

除此以外，你还有 pills 个神奇药丸，可以给 一个工人的力量值 增加 strength 。你可以决定给哪些工人使用药丸，但每个工人最多只能使用一片药丸。

给你下标从 0 开始的整数数组tasks 和 workers 以及两个整数 pills 和 strength ，请你返回最多有多少个任务可以被完成。

示例 1：

输入：tasks = [3,2,1], workers = [0,3,3], pills = 1, strength = 1
输出：3
解释：
我们可以按照如下方案安排药丸：
- 给 0 号工人药丸。
- 0 号工人完成任务 2（0 + 1 >= 1）
- 1 号工人完成任务 1（3 >= 2）
- 2 号工人完成任务 0（3 >= 3）

示例 2：

输入：tasks = [5,4], workers = [0,0,0], pills = 1, strength = 5
输出：1
解释：
我们可以按照如下方案安排药丸：
- 给 0 号工人药丸。
- 0 号工人完成任务 0（0 + 5 >= 5）

示例 3：

输入：tasks = [10,15,30], workers = [0,10,10,10,10], pills = 3, strength = 10
输出：2
解释：
我们可以按照如下方案安排药丸：
- 给 0 号和 1 号工人药丸。
- 0 号工人完成任务 0（0 + 10 >= 10）
- 1 号工人完成任务 1（10 + 10 >= 15）

示例 4：

输入：tasks = [5,9,8,5,9], workers = [1,6,4,2,6], pills = 1, strength = 5
输出：3
解释：
我们可以按照如下方案安排药丸：
- 给 2 号工人药丸。
- 1 号工人完成任务 0（6 >= 5）
- 2 号工人完成任务 2（4 + 5 >= 8）
- 4 号工人完成任务 3（6 >= 5）

提示：

n == tasks.length
m == workers.length
1 <= n, m <= 5 * 10⁴
0 <= pills <= m
0 <= tasks[i], workers[j], strength <= 10⁹

lightbulb

解题思路

方法一：贪心 + 二分查找

将任务按照完成时间从小到大排序，将工人按照能力从小到大排序。

假设我们要安排的任务数为 $x$ ，那么我们可以贪心地将前 $x$ 个任务分配给力量值最大的 $x$ 个工人。假设能完成任务数为 $x$ ，那么也一定能完成任务数为 $x-1$ ， $x-2$ ， $x-3$ ，…， $1$ ， $0$ 的情况。因此，我们可以使用二分查找的方法，找到最大的 $x$ ，使得能够完成任务数为 $x$ 的情况。

我们定义一个函数 $check(x)$ ，表示是否能够完成任务数为 $x$ 的情况。

函数 $check(x)$ 的实现如下：

从小到大遍历力量值最大的 $x$ 个工人，记当前遍历到的工人为 $j$ ，那么当前可选任务必须满足 $tasks[i] \leq workers[j] + strength$ 。

如果当前可选任务中要求力量值最小的一个 $task[i]$ 小于等于 $workers[j]$ ，那么第 $j$ 个工人不用吃药就可以完成任务 $task[i]$ 。否则，当前工人必须吃药，如果还有药丸，那么吃药，并且在当前可选任务中选择要求力量值最大的一个任务完成。否则，返回 false。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为任务数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

class Solution:
    def maxTaskAssign(
        self, tasks: List[int], workers: List[int], pills: int, strength: int
    ) -> int:
        def check(x):
            i = 0
            q = deque()
            p = pills
            for j in range(m - x, m):
                while i < x and tasks[i] <= workers[j] + strength:
                    q.append(tasks[i])
                    i += 1
                if not q:
                    return False
                if q[0] <= workers[j]:
                    q.popleft()
                elif p == 0:
                    return False
                else:
                    p -= 1
                    q.pop()
            return True

        n, m = len(tasks), len(workers)
        tasks.sort()
        workers.sort()
        left, right = 0, min(n, m)
        while left < right:
            mid = (left + right + 1) >> 1
            if check(mid):
                left = mid
            else:
                right = mid - 1
        return left

speed

复杂度分析

指标	值
时间	O(n \log n + m \log m + \min(m, n) \log^2 \min(m, n))
空间	O(\log n + \log m + \min(m, n))

psychology

面试官常问的追问

外企场景

question_mark
Checks the candidate's ability to optimize solutions for large input sizes.
question_mark
Assesses the ability to leverage binary search in an unconventional problem setting.
question_mark
Evaluates the understanding of greedy algorithms and task allocation optimization.

warning

常见陷阱

外企场景

error
Forgetting to sort both the tasks and workers arrays before applying the binary search.
error
Misapplying the binary search to the wrong range of possible solutions, resulting in incorrect assignments.
error
Not optimizing the pill distribution to maximize the number of tasks completed.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the magical pills have a variable effect on worker strength?
arrow_right_alt
How would the solution change if multiple workers can be assigned to a single task?
arrow_right_alt
How would you modify the solution if the number of magical pills is unlimited?

help

常见问题

外企场景

继续练习

#2234 花园的最大总美丽值 #2271 毯子覆盖的最多白色砖块数 #1838 最高频元素的频数