Hard
题目描述
给你 n 个任务和 m 个工人。每个任务需要一定的力量值才能胜任，第 i 个任务需要 tasks[i] 的力量才能胜任。每个工人的力量值为 workers[j] ，表示这个工人的力量值。每个工人只能被安排到一个任务上，但是一个任务可以无人安排。
除此以外，你还有 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）
最后一个药丸没有给出，因为它不会使任何工人强大到足以完成最后一个任务。
提示：
n == tasks.lengthm == workers.length1 <= n, m <= 5 * 10^40 <= pills <= m0 <= tasks[i], workers[j], strength <= 10^9
解题思路
这是一道典型的二分答案 + 贪心验证的问题。
核心思路：
二分答案：能完成的任务数具有单调性，如果能完成 k 个任务，那么一定能完成 k-1 个任务。因此可以二分枚举答案。
贪心验证：对于固定的任务数 k，需要验证是否可行。关键洞察是应该优先完成最简单的 k 个任务，这样成功概率最大。
任务分配策略：
- 将任务和工人都按力量值排序
- 对于前 k 个最简单的任务，使用双端队列维护可用工人
- 对每个任务，优先使用刚好能完成的工人（不使用药丸）
- 如果没有合适工人，使用药丸让最弱的能胜任工人完成任务
具体算法：
- 对任务升序排序，对工人降序排序
- 使用双端队列，从强到弱加入能完成当前任务的工人
- 对每个任务：先尝试不用药丸的最弱工人，再尝试用药丸的最弱工人
- 贪心原则：能不用药丸就不用，用药丸时选择最弱的工人
这种方法的时间复杂度为 O(n log n + m log m + k log k)，其中 k 是二分的范围。
代码实现
class Solution {
public:
int maxTaskAssign(vector<int>& tasks, vector<int>& workers, int pills, int strength) {
sort(tasks.begin(), tasks.end());
sort(workers.begin(), workers.end(), greater<int>());
int left = 0, right = min((int)tasks.size(), (int)workers.size());
while (left < right) {
int mid = (left + right + 1) / 2;
if (canComplete(tasks, workers, mid, pills, strength)) {
left = mid;
} else {
right = mid - 1;
}
}
return left;
}
private:
bool canComplete(vector<int>& tasks, vector<int>& workers, int k, int pills, int strength) {
deque<int> dq;
int j = 0;
int usedPills = 0;
for (int i = 0; i < k; i++) {
// 添加所有能完成当前任务的工人（可能需要药丸）
while (j < workers.size() && workers[j] + strength >= tasks[i]) {
dq.push_back(workers[j]);
j++;
}
// 如果队列中有工人能不用药丸完成任务
if (!dq.empty() && dq.back() >= tasks[i]) {
dq.pop_back(); // 使用最弱的能胜任的工人
}
// 否则需要使用药丸
else if (!dq.empty() && usedPills < pills) {
dq.pop_front(); // 使用最强的工人加药丸
usedPills++;
}
// 无法完成这个任务
else {
return false;
}
}
return true;
}
};
class Solution:
def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:
from collections import deque
tasks.sort()
workers.sort(reverse=True)
def canComplete(k):
dq = deque()
j = 0
used_pills = 0
for i in range(k):
# 添加所有能完成当前任务的工人（可能需要药丸）
while j < len(workers) and workers[j] + strength >= tasks[i]:
dq.append(workers[j])
j += 1
# 如果队列中有工人能不用药丸完成任务
if dq and dq[-1] >= tasks[i]:
dq.pop() # 使用最弱的能胜任的工人
# 否则需要使用药丸
elif dq and used_pills < pills:
dq.popleft() # 使用最强的工人加药丸
used_pills += 1
# 无法完成这个任务
else:
return False
return True
left, right = 0, min(len(tasks), len(workers))
while left < right:
mid = (left + right + 1) // 2
if canComplete(mid):
left = mid
else:
right = mid - 1
return left
public class Solution {
public int MaxTaskAssign(int[] tasks, int[] workers, int pills, int strength) {
Array.Sort(tasks);
Array.Sort(workers, (a, b) => b.CompareTo(a));
int left = 0, right = Math.Min(tasks.Length, workers.Length);
while (left < right) {
int mid = (left + right + 1) / 2;
if (CanComplete(tasks, workers, mid, pills, strength)) {
left = mid;
} else {
right = mid - 1;
}
}
return left;
}
private bool CanComplete(int[] tasks, int[] workers, int k, int pills, int strength) {
var dq = new LinkedList<int>();
int j = 0;
int usedPills = 0;
for (int i = 0; i < k; i++) {
// 添加所有能完成当前任务的工人（可能需要药丸）
while (j < workers.Length && workers[j] + strength >= tasks[i]) {
dq.AddLast(workers[j]);
j++;
}
// 如果队列中有工人能不用药丸完成任务
if (dq.Count > 0 && dq.Last.Value >= tasks[i]) {
dq.RemoveLast(); // 使用最弱的能胜任的工人
}
// 否则需要使用药丸
else if (dq.Count > 0 && usedPills < pills) {
dq.RemoveFirst(); // 使用最强的工人加药丸
usedPills++;
}
// 无法完成这个任务
else {
return false;
}
}
return true;
}
}
var maxTaskAssign = function(tasks, workers, pills, strength) {
tasks.sort((a, b) => a - b);
workers.sort((a, b) => b - a);
const canComplete = (k) => {
const dq = [];
let j = 0;
let usedPills = 0;
for (let i = 0; i < k; i++) {
// 添加所有能完成当前任务的工人（可能需要药丸）
while (j < workers.length && workers[j] + strength >= tasks[i]) {
dq.push(workers[j]);
j++;
}
// 如果队列中有工人能不用药丸完成任务
if (dq.length > 0 && dq[dq.length - 1] >= tasks[i]) {
dq.pop(); // 使用最弱的能胜任的工人
}
// 否则需要使用药丸
else if (dq.length > 0 && usedPills < pills) {
dq.shift(); // 使用最强的工人加药丸
usedPills++;
}
// 无法完成这个任务
else {
return false;
}
}
return true;
};
let left = 0, right = Math.min(tasks.length, workers.length);
while (left < right) {
const mid = Math.floor((left + right + 1) / 2);
if (canComplete(mid)) {
left = mid;
} else {
right = mid - 1;
}
}
return left;
};
复杂度分析
| 复杂度类型 | 分析 |
|---|---|
| 时间复杂度 | O((n + m) log(min(n, m))) |
| 空间复杂度 | O(m) |
时间复杂度分析：
- 排序：O(n log n + m log m)
- 二分答案：O(log(min(n, m))) 次
- 每次验证：O(n + m)
- 总时间复杂度：O((n + m) log(min(n, m)))
空间复杂度分析：
- 双端队列最多存储 m 个工人：O(m)