点击获取AI摘要

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

给你 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^4$
0 <= pills <= m
0 <= tasks[i], workers[j], strength <= $10^9$

问题分析

任务：有 $n$ 个任务，任务力量需求数组为 tasks；有 $m$ 名工人，力量数组为 workers。
药丸：你有 pills 颗药，每颗可以让一个工人的力量增加 strength，且每个工人最多只能吃一颗。
目标：在最优分配下，最多能完成多少个任务。

算法思路

排序
- 将 tasks 从小到大排序，编号后更容易按难度取子区间；
- 将 workers 从小到大排序，方便挑最强和二分查找。
二分答案 $k$ $k$
- 答案 $k$ 最多不会超过 $\min(n, m)$ 。
- 我们在区间 $[0, \min(n,m)]$ 上二分查找最大的可行 $k$ 。
可行性验证 can_do(k)
- 取子集：对尝试完成的前 $k$ 个最小任务 tasks[0..k-1]，对应后 $k$ 个最强工人 workers[m-k..m-1]。
- 维护有序容器：把这 $k$ 名工人放入一个支持「删最大」「按需求二分查找最小满足」操作的有序结构（如 Python bisect+list 或者 sortedcontainers.SortedList）。
- 从 hardest 到 easiest：为了节省药丸，我们先处理需求最高的任务。对每个任务 $t$ $t$ ：
  - 如果容器中最大力量 $\ge t$ ，直接分配该工人（弹出最大），不消耗药丸。
  - 否则，需要用药：找容器中最小的工人 $w$ 满足 $w + strength \ge t$ （用二分查找找第一个 $\ge t - strength$ ），若找不到或药丸已用完，则失败；否则分配、药丸减一。
- 如果所有 $k$ 个任务都能分配完，can_do(k)=True，如果在分配过程中药丸数超过 pills，或找不到可用工人，则 can_do(k) 返回 False。

时间复杂度

时间复杂度
- 排序： $O(n\log n + m\log m)$
- 二分： $O(\log \min(n,m))$ 次可行性验证
- 每次验证：最多 $k$ 次删除/查找，每次 $O(\log k)$ ，所以 $O(k\log k)$
- 总计：
  
  $O\bigl((n+m)\log(n+m)\;+\;\log\min(n,m)\times\min(n,m)\log m\bigr).$
空间复杂度 : 排序原地排序外，额外使用 O(m) 存储可用工人列表。

代码分解

先解决最难的任务，这样能保证弱工人和药丸优先用于最“吃力”的配对，若连最难的都配不上，k 肯定不可行。

使用 sortedcontainers.SortedList，支持 sl.pop(-1)、sl.bisect_left()、sl.pop(idx) 都是 $O(\log k)$

用「上取整」的 mid 方案：

lo, hi = 0, min(n, m)
while lo < hi:
    mid = (lo + hi + 1) // 2
    if can_do(mid):
        lo = mid
    else:
        hi = mid - 1
return lo

代码实现

from sortedcontainers import SortedList
from bisect import bisect_left

class Solution:
    def maxTaskAssign(self, tasks, workers, pills, strength):
        tasks.sort()
        workers.sort()

        def can_do(k):
            # 取最强 k 工人，放入可排序列表
            avail = SortedList(workers[-k:])
            pills_left = pills
            # 从最难任务到最简单
            for t in reversed(tasks[:k]):
                # 如果最强工人够力
                if avail and avail[-1] >= t:
                    avail.pop(-1)
                else:
                    # 用药分配
                    if pills_left == 0:
                        return False
                    # 找最弱且加药后能胜任的工人,需要 w >= t - strength
                    need = t - strength
                    idx = avail.bisect_left(need)
                    if idx == len(avail):
                        return False
                    # 分配并消耗
                    avail.pop(idx)
                    pills_left -= 1
            return True
        # 二分最大 k
        lo, hi = 0, min(len(tasks), len(workers))
        while lo < hi:
            mid = (lo + hi + 1) // 2
            if can_do(mid):
                lo = mid
            else:
                hi = mid - 1
        return lo

以tasks = [3,2,1], workers = [0,3,3], pills = 1, strength = 1为例：

二分过程	任务子集	工人子集	药丸使用情况	分配过程	结果判断
初始状态(排序后)	[1,2,3]	[0,3,3]	1	-	-
尝试 mid=2	[1,2]	[0,3,3]	1	1. 较大任务 2 分配给最大工人 3 ≥ 2 → 不用药，弹出 3。 2. 任务 1 分配给最大工人 3 ≥ 1 → 不用药，弹出 3。	成功 → `can_do(2)=True`，二分上界提升到 2
尝试 mid=3	[1,2,3]	[0,3,3]	1	1. 任务 3 分配给最大工人 3 ≥ 3 → 不用药，弹出 3，剩 `[0,3]`。 2. 任务 2 分配给最大工人 3 ≥ 2 → 不用药，弹出 3，剩 `[0]`。 3. 任务 1 分配给唯一工人 0 < 1 → 需要用药，查找最小 $w\ge 1-1=0$ ，找到 0，用药后分配成功。	成功 → `can_do(3)=True`，最终答案 3