[LeetCode] 每日一题 2071. 你可以安排的最多任务数目（逆向思维 + 贪心 + 二分查找）
题目描述
给你 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.lengthm == workers.length1 <= n, m <= 5 * 10^40 <= pills <= m0 <= tasks[i], workers[j], strength <= 10^9
解题思路
这题初看非常容易陷入暴力尝试的陷阱，像我一开始那样想用排序加贪心硬怼，但始终缺少系统性的切入点。参考了其他题解之后，受到了“逆向思维 + 二分答案”的启发，顿时豁然开朗。
核心思路是：倒过来问，如果我们想完成 k 个任务，是否有一种安排方式可以实现？只要我们能构造一个 check(k) 的判断函数，那么答案就可以通过 二分查找在 [0, min(tasks.length, workers.length)] 区间内快速定位。
接下来是关键的 check(k) 判断逻辑。这里需要一些贪心的策略：
将任务和工人分别升序排列；
将力量最大的 k 个工人分配给力量要求最小的 k 个任务，也就是优先完成最简单的任务；
对于当前工人，如果他不用药丸就能完成最小任务，就直接分配；
否则判断是否还能使用药丸（药丸最多用
pills次，每人只能用一次）；若可以用药丸，就尝试完成最难任务；
通过一个双向队列（Deque）暂存可分配的任务，灵活从两端取任务完成。
通过上述 check 函数，我们就能用经典的“二分 + 可行性判断”思路解决这个问题。
代码实现
class Solution {
public int maxTaskAssign(int[] tasks, int[] workers, int pills, int strength) {
Arrays.sort(tasks);
Arrays.sort(workers);
int left = 0;
int right = Math.min(tasks.length, workers.length) + 1;
while (left + 1 < right) {
int mid = (left + right) / 2;
if (check(tasks, workers, pills, strength, mid)) {
left = mid;
} else {
right = mid;
}
}
return left;
}
private boolean check(int[] tasks, int[] workers, int pills, int strength, int k) {
Deque<Integer> valid = new LinkedList<>();
int taskIndex = 0;
int n = workers.length;
for (int workerIndex = workers.length - k; workerIndex < n; workerIndex++) {
int worker = workers[workerIndex];
while (taskIndex < k && tasks[taskIndex] <= worker + strength) {
valid.addLast(tasks[taskIndex]);
taskIndex++;
}
if (valid.isEmpty()) {
return false;
}
if (worker >= valid.peekFirst()) {
valid.pollFirst();
continue;
}
if (pills == 0) {
return false;
}
pills--;
valid.pollLast();
}
return true;
}
}复杂度分析
时间复杂度：O(n log n + m log m + log(min(n, m)) * k) 🧠
排序部分为 O(n log n + m log m)
二分次数为 log(min(n, m))
每次 check 最多遍历 k 个任务和工人，最多 O(k)
空间复杂度：O(k) 💾
主要是用于双向队列存储当前可分配任务
总结
这题很有代表性，融合了二分、贪心和双指针/队列等常见技巧，尤其是“从结果出发，验证可行性”的逆向思维让我印象深刻。像我这样平时习惯从输入出发暴力枚举的人，这种解题思路值得反复练习 🔁。另外，题中对药丸使用的限制条件也提醒我们，在资源受限的情况下，贪心策略如何最大化收益，是构建 check 函数的关键。
希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。