跳转至

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.length
  • m == workers.length
  • 1 <= n, m <= 5 * 104
  • 0 <= pills <= m
  • 0 <= tasks[i], workers[j], strength <= 109

解法

方法一：贪心 + 二分查找

将任务按照完成时间从小到大排序，将工人按照能力从小到大排序。

假设我们要安排的任务数为 \(x\)，那么我们可以贪心地将前 \(x\) 个任务分配给力量值最大的 \(x\) 个工人。假设能完成任务数为 \(x\)，那么也一定能完成任务数为 \(x-1\)，\(x-2\)，\(x-3\)，…，\(1\)，\(0\) 的情况。因此，我们可以使用二分查找的方法，找到最大的 \(x\)，使得能够完成任务数为 \(x\) 的情况。

我们定义一个函数 \(check(x)\)，表示是否能够完成任务数为 \(x\) 的情况。

函数 \(check(x)\) 的实现如下：

从小到大遍历力量值最大的 \(x\) 个工人，记当前遍历到的工人为 \(j\)，那么当前可选任务必须满足 \(tasks[i] \leq workers[j] + strength\)。

如果当前可选任务中要求力量值最小的一个 \(task[i]\) 小于等于 \(workers[j]\)，那么第 \(j\) 个工人不用吃药就可以完成任务 \(task[i]\)。否则，当前工人必须吃药，如果还有药丸，那么吃药，并且在当前可选任务中选择要求力量值最大的一个任务完成。否则，返回 false。

时间复杂度 \(O(n \times \log n)\)，空间复杂度 \(O(n)\)。其中 \(n\) 为任务数。

 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
class Solution: def maxTaskAssign( self, tasks: List[int], workers: List[int], pills: int, strength: int ) -> int: def check(x): i = 0 q = deque() p = pills for j in range(m - x, m): while i < x and tasks[i] <= workers[j] + strength: q.append(tasks[i]) i += 1 if not q: return False if q[0] <= workers[j]: q.popleft() elif p == 0: return False else: p -= 1 q.pop() return True n, m = len(tasks), len(workers) tasks.sort() workers.sort() left, right = 0, min(n, m) while left < right: mid = (left + right + 1) >> 1 if check(mid): left = mid else: right = mid - 1 return left 
 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 {  private int[] tasks;  private int[] workers;  private int strength;  private int pills;  private int m;  private int n;  public int maxTaskAssign(int[] tasks, int[] workers, int pills, int strength) {  Arrays.sort(tasks);  Arrays.sort(workers);  this.tasks = tasks;  this.workers = workers;  this.strength = strength;  this.pills = pills;  n = tasks.length;  m = workers.length;  int left = 0, right = Math.min(m, n);  while (left < right) {  int mid = (left + right + 1) >> 1;  if (check(mid)) {  left = mid;  } else {  right = mid - 1;  }  }  return left;  }  private boolean check(int x) {  int i = 0;  Deque<Integer> q = new ArrayDeque<>();  int p = pills;  for (int j = m - x; j < m; ++j) {  while (i < x && tasks[i] <= workers[j] + strength) {  q.offer(tasks[i++]);  }  if (q.isEmpty()) {  return false;  }  if (q.peekFirst() <= workers[j]) {  q.pollFirst();  } else if (p == 0) {  return false;  } else {  --p;  q.pollLast();  }  }  return true;  } } 
 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
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());  int n = tasks.size(), m = workers.size();  int left = 0, right = min(m, n);  auto check = [&](int x) {  int p = pills;  deque<int> q;  int i = 0;  for (int j = m - x; j < m; ++j) {  while (i < x && tasks[i] <= workers[j] + strength) {  q.push_back(tasks[i++]);  }  if (q.empty()) {  return false;  }  if (q.front() <= workers[j]) {  q.pop_front();  } else if (p == 0) {  return false;  } else {  --p;  q.pop_back();  }  }  return true;  };  while (left < right) {  int mid = (left + right + 1) >> 1;  if (check(mid)) {  left = mid;  } else {  right = mid - 1;  }  }  return left;  } }; 
 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
func maxTaskAssign(tasks []int, workers []int, pills int, strength int) int {  sort.Ints(tasks)  sort.Ints(workers)  n, m := len(tasks), len(workers)  left, right := 0, min(m, n)  check := func(x int) bool {  p := pills  q := []int{}  i := 0  for j := m - x; j < m; j++ {  for i < x && tasks[i] <= workers[j]+strength {  q = append(q, tasks[i])  i++  }  if len(q) == 0 {  return false  }  if q[0] <= workers[j] {  q = q[1:]  } else if p == 0 {  return false  } else {  p--  q = q[:len(q)-1]  }  }  return true  }  for left < right {  mid := (left + right + 1) >> 1  if check(mid) {  left = mid  } else {  right = mid - 1  }  }  return left } 
 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 53 54 55 56 57 58
function maxTaskAssign(  tasks: number[],  workers: number[],  pills: number,  strength: number, ): number {  tasks.sort((a, b) => a - b);  workers.sort((a, b) => a - b);  const n = tasks.length;  const m = workers.length;  const check = (x: number): boolean => {  const dq = new Array<number>(x);  let head = 0;  let tail = 0;  const empty = () => head === tail;  const pushBack = (val: number) => {  dq[tail++] = val;  };  const popFront = () => {  head++;  };  const popBack = () => {  tail--;  };  const front = () => dq[head];  let i = 0;  let p = pills;  for (let j = m - x; j < m; j++) {  while (i < x && tasks[i] <= workers[j] + strength) {  pushBack(tasks[i]);  i++;  }  if (empty()) return false;  if (front() <= workers[j]) {  popFront();  } else {  if (p === 0) return false;  p--;  popBack();  }  }  return true;  };  let [left, right] = [0, Math.min(n, m)];  while (left < right) {  const mid = (left + right + 1) >> 1;  if (check(mid)) left = mid;  else right = mid - 1;  }  return left; }

评论