05 August 2008
你可以安排的最多任务数目
给你 n 个任务和 m 个工人。每个任务需要一定的力量值才能完成，需要的力量值保存在下标从 0 开始的整数数组 tasks 中，第 i 个任务需要 tasks[i] 的力量才能完成。每个工人的力量值保存在下标从 0 开始的整数数组 workers 中，第 j 个工人的力量值为 workers[j] 。每个工人只能完成 一个 任务，且力量值需要 大于等于 该任务的力量要求值（即 workers[j] >= tasks[i] ）。
除此以外，你还有 pills 个神奇药丸，可以给 一个工人的力量值 增加 strength 。你可以决定给哪些工人使用药丸，但每个工人 最多 只能使用 一片 药丸。
给你下标从 0 开始的整数数组tasks 和 workers 以及两个整数 pills 和 strength ，请你返回 最多 有多少个任务可以被完成。
二分，加了双端队列的优化
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Solution {
public int maxTaskAssign(int[] tasks, int[] workers, int pills, int strength) {
Arrays.sort(tasks);
TreeMap<Integer, Integer> workerMap = new TreeMap<>();
for (int worker : workers) {
workerMap.put(worker, workerMap.getOrDefault(worker, 0) + 1);
}
int ans = 0;
int l = 0, r = tasks.length - 1;
while (l <= r) {
int mid = (l + r) >> 1;
if (helper(tasks, new TreeMap<>(workerMap), pills, strength, mid)) {
ans = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
return ans + 1;
}
private boolean helper(int[] tasks, TreeMap<Integer, Integer> workerMap, int pills, int strength, int mid) {
for (int i = mid; i >= 0; i--) {
Map.Entry<Integer, Integer> ceilingEntry = workerMap.ceilingEntry(tasks[i]);
if (ceilingEntry != null) {
//不使用药丸
if (ceilingEntry.getValue() > 1) {
workerMap.put(ceilingEntry.getKey(), ceilingEntry.getValue() - 1);
} else {
workerMap.remove(ceilingEntry.getKey());
}
} else {
//使用药丸
if (pills == 0) {
return false;
}
pills--;
Map.Entry<Integer, Integer> entry = workerMap.ceilingEntry(tasks[i] - strength);
if (entry != null) {
if (entry.getValue() > 1) {
workerMap.put(entry.getKey(), entry.getValue() - 1);
} else {
workerMap.remove(entry.getKey());
}
} else {
return false;
}
}
}
return true;
}
}