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

这篇具有很好参考价值的文章主要介绍了【贪心算法】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 <= n, m <= 5 * 104
    0 <= pills <= m
    0 <= tasks[i], workers[j], strength <= 109

分析

时间复杂度

O(lognnlogn)。二分查找可以完成的任务数,时间复杂度O(logn);枚举任务,时间复杂度O(n);每个任务二分查找,时间复杂度O(logn)。

二分查找

0个任务一定可以完成,随着任务数增加,变得不可完成。寻找最后一个可以完成任务的doNum,左闭右开空间。

完成doNum个任务

最强的doNum个工人是否能完成最简单的doNum个任务。从困难到容易枚举任务,如果有工人能完成,则直接完成。否则,吃药丸完成。无论是否吃药丸,在能完成任务的情况下,派最弱的人。

为什么能不吃药丸,就不吃药丸

假定任务i,b吃药丸才能完成,c可直接完成。
方案一:c直接完成。
方案二:b吃药丸完成。
除掉相同的工人和药丸。
方案一:b和一片药丸。
方案二:c。
如果方案二,能完成任务,则方案一也能完成任务。b吃药后,能完成余下任意任务。任务是从难到容易的。
注意:反之不成立。因为药丸可以给b以外的工人吃。

代码

核心代码

class Solution {
public:
int maxTaskAssign(vector& tasks, vector& workers, const int pills, const int strength) {
auto Can = [&](const int doNum)
{
int iNeedPill = 0;
std::multiset setWork(workers.rbegin() , workers.rbegin()+doNum);
for (int i = doNum - 1; i >= 0; i–)
{
auto it = setWork.lower_bound(tasks[i]);
if (setWork.end() != it)
{
setWork.erase(it);
continue;
}
if (iNeedPill >= pills)
{//没药丸了
return false;
}
it = setWork.lower_bound(tasks[i] - strength);
if (setWork.end() == it)
{
return false;//吃了药丸也无法完成任务
}
setWork.erase(it);
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;
}
};

测试用例

template
void Assert(const vector& v1, const vector& v2)
{
if (v1.size() != v2.size())
{
assert(false);
return;
}
for (int i = 0; i < v1.size(); i++)
{
assert(v1[i] == v2[i]);
}
}

template
void Assert(const T& t1, const T& t2)
{
assert(t1 == t2);
}

int main()
{
vector tasks, workers;
int pills, strength, res;
{
Solution slu;
tasks = { 3, 2, 1 }, workers = { 0, 3, 3 }, pills = 1, strength = 1;
auto res = slu.maxTaskAssign(tasks, workers, pills, strength);
Assert(3, res);
}
{
Solution slu;
tasks = { 5, 4 }, workers = { 0, 0, 0 }, pills = 1, strength = 5;
auto res = slu.maxTaskAssign(tasks, workers, pills, strength);
Assert(1, res);
}
{
Solution slu;
tasks = { 10, 15, 30 }, workers = { 0, 10, 10, 10, 10 }, pills = 3, strength = 10;
auto res = slu.maxTaskAssign(tasks, workers, pills, strength);
Assert(2, res);
}
{
Solution slu;
tasks = { 5, 9, 8, 5, 9 }, workers = { 1, 6, 4, 2, 6 }, pills = 1, strength = 5;
auto res = slu.maxTaskAssign(tasks, workers, pills, strength);
Assert(3, res);
}

//CConsole::Out(res);

}

2023年3月版

class Solution {
public:
int maxTaskAssign(vector& tasks, vector& workers, int pills, int strength) {
const int iNum = min(tasks.size(), workers.size());
std::sort(tasks.begin(), tasks.end());
std::sort(workers.begin(), workers.end());
return Rev(0, iNum + 1, tasks, workers, pills, strength); }
int Rev(int iMin, int iMax, const vector& tasks, const vector& workers, int pills, int strength)
{
if (iMin + 1 == iMax)
{
return iMin;
}
const int iMid = (iMin + iMax) / 2;
if (Can(iMid, tasks, workers, pills, strength))
{
return Rev(iMid, iMax, tasks, workers, pills, strength);
}
return Rev(0, iMid, tasks, workers, pills, strength);
}
bool Can(int iFinishNum, const vector& tasks, const vector& workers, int pills, int strength)
{
std::multiset setWorks(workers.begin() + workers.size() - iFinishNum, workers.end());
for (int i = iFinishNum - 1; i >= 0;i–)
{
if (tasks[i] <= *setWorks.rbegin())
{
setWorks.erase(std::prev(setWorks.end()));
continue;
}
if (pills <= 0)
{
return false;
}
auto it = setWorks.lower_bound(tasks[i] - strength);
if (setWorks.end() == it )
{
return false;
}
pills–;
setWorks.erase(it);
}
return true;
}
};

优化

如果有工人,能直接完成。则选择任意一个能完成的工人,不必选择最弱的工人。因为任务是越来越容易,能完成当前任务,则能完成之后的任意任务。双向队列que记录所有吃药丸后能完成当前任务的工人,升序排列。先判断队尾能否直接完成,否则判断队首能否吃药丸完成。

代码

class Solution {
public:
	int maxTaskAssign(vector<int>& tasks, vector<int>& workers, const int pills, const int strength) {
		auto Can = [&](const int doNum)
		{
			int iNeedPill = 0;
			std::vector<int> vWork(workers.begin()+workers.size()- doNum , workers.end());//派出的工人
			std::deque<int> que;
			for (int i = doNum - 1, j = i; i >= 0; i--)
			{		
				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;
	}
};

【贪心算法】LeetCode2071:你可以安排的最多任务数目,# 算法题,数据结构与算法,贪心算法,算法,c++,leetcode,二分查找,双向队列

扩展阅读

视频课程

有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步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

【贪心算法】LeetCode2071:你可以安排的最多任务数目,# 算法题,数据结构与算法,贪心算法,算法,c++,leetcode,二分查找,双向队列文章来源地址https://www.toymoban.com/news/detail-752112.html

到了这里,关于【贪心算法】LeetCode2071:你可以安排的最多任务数目的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 2023-09-02 LeetCode每日一题(最多可以摧毁的敌人城堡数目)

    点击跳转到题目位置 给你一个长度为 n ,下标从 0 开始的整数数组 forts ,表示一些城堡。forts[i] 可以是 -1 ,0 或者 1 ,其中: -1 表示第 i 个位置 没有 城堡。 0 表示第 i 个位置有一个 敌人 的城堡。 1 表示第 i 个位置有一个你控制的城堡。 现在,你需要决定,将你的军队从

    2024年02月10日
    浏览(41)
  • 算法分析与设计-会场安排问题(贪心)(通俗易懂,附源码和图解,含贪心选择性质和最优子结构性质的证明)(c++)

    (一)题目 问题描述 假设在足够多的会场里安排一批活动,并希望使用尽可能少的会场。设计一个有效的贪心算法进行安排。(这个问题实际上是著名的图着色问题。若将每个活动作为图的一个顶点,不相容活动间用边相连。使相邻顶点有着不同颜色的最小着色数,相当于

    2024年02月07日
    浏览(94)
  • 句子中的最多单词数

    🎈不知道大家对于算法的学习是一个怎样的心态呢?为了面试还是因为兴趣?不管是出于什么原因,算法学习需要持续保持。 一个 句子 由一些 单词 以及它们之间的单个空格组成,句子的开头和结尾不会有多余空格。 给你一个字符串数组 sentences ,其中 sentences[i] 表示

    2024年01月17日
    浏览(33)
  • 数据结构实验任务六 :基于 Dijsktra 算法的最短路径求解

    本次代码为实验六:基于 Dijsktra 算法的最短路径求解实现。本实验的重点在于对于Dijsktra算法的理解。有关Dijsktra的资料可以参考有关博文: 图论:Dijkstra算法——最详细的分析,图文并茂,一次看懂!-CSDN博客 以下附上实现代码: 以上代码仅供参考,欢迎交流。

    2024年02月04日
    浏览(50)
  • 会场安排问题(贪心)

    2024年03月26日
    浏览(40)
  • 算法沉淀——贪心算法二(leetcode真题剖析)

    题目链接:https://leetcode.cn/problems/longest-increasing-subsequence/ 给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。 子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如, [3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。 示例 1: 示

    2024年03月19日
    浏览(51)
  • 算法沉淀——贪心算法三(leetcode真题剖析)

    题目链接:https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/ 给你一个整数数组 prices ,其中 prices[i] 表示某支股票第 i 天的价格。 在每一天,你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买,然后在 同一天 出售。 返回 你能获得

    2024年03月24日
    浏览(39)
  • 算法沉淀——贪心算法五(leetcode真题剖析)

    题目链接:https://leetcode.cn/problems/jump-game-ii/ 给定一个长度为 n 的 0 索引 整数数组 nums 。初始位置为 nums[0] 。 每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说,如果你在 nums[i] 处,你可以跳转到任意 nums[i + j] 处: 0 = j = nums[i] i + j n 返回到达 nums[n - 1] 的最小跳跃次

    2024年04月11日
    浏览(49)
  • 算法沉淀——贪心算法一(leetcode真题剖析)

    贪心算法(Greedy Algorithm)是一种基于贪心策略的优化算法,它通常用于求解最优化问题,每一步都选择当前状态下的最优解,以期望通过局部最优的选择最终达到全局最优。贪心算法的思想是在每一步都做出在当前状态下局部最优的选择,而不考虑未来可能造成的影响。 在

    2024年03月08日
    浏览(51)
  • 算法沉淀——贪心算法七(leetcode真题剖析)

    题目链接:https://leetcode.cn/problems/integer-replacement/ 给定一个正整数 n ,你可以做如下操作: 如果 n 是偶数,则用 n / 2 替换 n 。 如果 n 是奇数,则可以用 n + 1 或 n - 1 替换 n 。 返回 n 变为 1 所需的 最小替换次数 。 示例 1: 示例 2: 示例 3: 提示: 1 = n = 2^31 - 1 思路 这里我们

    2024年03月23日
    浏览(52)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包