[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 ，请你返回 最多 有多少个任务可以被完成。

题目链接

https://leetcode.cn/problems/maximum-number-of-tasks-you-can-assign

示例输入

示例 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

解题思路

这题初看非常容易陷入暴力尝试的陷阱，像我一开始那样想用排序加贪心硬怼，但始终缺少系统性的切入点。参考了其他题解之后，受到了“逆向思维 + 二分答案”的启发，顿时豁然开朗。

核心思路是：倒过来问，如果我们想完成 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 函数的关键。

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。