【贪心算法】LeetCode2071:你可以安排的最多任务数目

作者推荐

[二分查找]LeetCode2040:两个有序数组的第 K 小乘积

本文涉及的基础知识点

二分查找算法合集

题目

给你 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 public: int maxTaskAssign(vector auto Can = [&](const int doNum) { int iNeedPill = 0; std::vector while ((j=0)&&(vWork[j]+strength = tasks[i])) { que.emplace_front(vWork[j--]); } if (que.empty()) { return false;//没有共人能完成任务 } if (que.back() = tasks[i]) { que.pop_back(); continue; } if (iNeedPill >= pills) {//没药丸了 return false; } que.pop_front(); iNeedPill++; } return true; }; sort(tasks.begin(), tasks.end()); sort(workers.begin(), workers.end()); int n = min(tasks.size(), workers.size()); int left = 0, right = n + 1;//左闭右开 while (right - left > 1) { const auto mid = left + (right - left) / 2; if (Can(mid)) { left = mid; } else { right = mid; } } return left; } };

  

  扩展阅读

  视频课程

  有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。

  https://edu.csdn.net/course/detail/38771

  如何你想快

  速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程

  https://edu.csdn.net/lecturer/6176

  相关下载

  想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版

  https://download.csdn.net/download/he_zhidan/88348653

  我想对大家说的话
  闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
  子墨子言之：事无终始，无务多业

  。也就是我们常说的专业的人做专业的事。 |

  |如果程序是一条龙，那算法就是他的是睛|

  测试环境

  操作系统：win7 开发环境： VS2019 C++17

  或者 操作系统：win10 开发环境：

  VS2022 C++17