企业网站建设常见问题,购物商城类app开发,tcn短网址在线生成,科技局网站建设方案作者推荐
【动态规划】【广度优先】LeetCode2258:逃离火灾
本文涉及的基础知识点
二分查找算法合集 有序向量的二分查找#xff0c;向量只会在尾部增加删除。
题目
你有一台电脑#xff0c;它可以 同时 运行无数个任务。给你一个二维整数数组 tasks #xff0c;其中 ta…作者推荐
【动态规划】【广度优先】LeetCode2258:逃离火灾
本文涉及的基础知识点
二分查找算法合集 有序向量的二分查找向量只会在尾部增加删除。
题目
你有一台电脑它可以 同时 运行无数个任务。给你一个二维整数数组 tasks 其中 tasks[i] [starti, endi, durationi] 表示第 i 个任务需要在 闭区间 时间段 [starti, endi] 内运行 durationi 个整数时间点但不需要连续。 当电脑需要运行任务时你可以打开电脑如果空闲时你可以将电脑关闭。 请你返回完成所有任务的情况下电脑最少需要运行多少秒。 示例 1 输入tasks [[2,3,1],[4,5,1],[1,5,2]] 输出2 解释
第一个任务在闭区间 [2, 2] 运行。第二个任务在闭区间 [5, 5] 运行。第三个任务在闭区间 [2, 2] 和 [5, 5] 运行。 电脑总共运行 2 个整数时间点。 示例 2 输入tasks [[1,3,2],[2,5,3],[5,6,2]] 输出4 解释第一个任务在闭区间 [2, 3] 运行第二个任务在闭区间 [2, 3] 和 [5, 5] 运行。第三个任务在闭区间 [5, 6] 运行。 电脑总共运行 4 个整数时间点。 参数范围 1 tasks.length 2000 tasks[i].length 3 1 starti, endi 2000 1 durationi endi - starti 1
分析
时间复杂度: O(nlogn)。枚举任务时间复杂度O(n)每个任务二分查找时间复杂度O(logn)。将任务按结束时间排序的时间复杂度也是O(nlogn)。 如果运行的时间不够尽量在靠近结束时间的运行。
变量解析
vEndLenTotalLen电脑运行的时间段升序时间段间无重叠。第一个元素结束时间第二个元素本次运行时间第三个时间段本时间段及之前的时间段总运行时间。iHasLen已已有时间本次任务能运行的时间。(get0(*it) - max(curBegin, v[0]) 1)当前任务it时间段能运行的时间curNotUseit及之前的时间段当前任务无法运行的时间。it后的时间段当前任务一定能运行。(v[1] - get0(vEndLenTotalLen.back()) iNeedAdd)新加的时间段需要和之前的时间段合并么
代码
核心代码
class Solution {
public:int findMinimumTime(vectorvectorint tasks) {sort(tasks.begin(), tasks.end(), [](const auto v1, const auto v2) {return v1[1] v2[1]; });vectortupleint, int,int vEndLenTotalLen;for (const auto v : tasks){const auto it std::lower_bound(vEndLenTotalLen.begin(), vEndLenTotalLen.end(),v[0], [](const auto t, const int i) {return get0(t) i; });int iHasLen 0;if ((vEndLenTotalLen.end() ! it)){const int curBegin get0(*it) - get1(*it) 1;const int curNotUse get2(*it) - (get0(*it) - max(curBegin, v[0]) 1);iHasLen get2(vEndLenTotalLen.back()) - curNotUse;}int iNeedAdd v[2] - iHasLen;if (iNeedAdd 0 ){continue;}while (vEndLenTotalLen.size() (v[1] - get0(vEndLenTotalLen.back()) iNeedAdd)){iNeedAdd get1(vEndLenTotalLen.back());vEndLenTotalLen.pop_back();}vEndLenTotalLen.emplace_back(v[1], iNeedAdd, iNeedAdd (vEndLenTotalLen.empty() ? 0 : get2(vEndLenTotalLen.back())));}return get2(vEndLenTotalLen.back());}
};测试用例 templateclass T
void Assert(const vectorT v1, const vectorT v2)
{if (v1.size() ! v2.size()){assert(false);return;}for (int i 0; i v1.size(); i){assert(v1[i] v2[i]);}
}templateclass T
void Assert(const T t1, const T t2)
{assert(t1 t2);
}int main()
{vectorvectorint tasks;{Solution slu;tasks { {2,3,1},{4,5,1},{1,5,2} };auto res slu.findMinimumTime(tasks);Assert(2, res);}{Solution slu;tasks tasks { {1,3,2},{2,5,3},{5,6,2} };auto res slu.findMinimumTime(tasks);Assert(4, res);}
}2023年9月版
class Solution { public: int findMinimumTime(vectorvector tasks) { sort(tasks.begin(), tasks.end(), [](const vector v1, const vector v2) { return v1[1] v2[1]; }); std::multimapint, pairint, int mEndToLenTotalLen; int iTotalLen 0; for (const auto v : tasks) { int lenShare 0;//可以和前面共享的时间段 auto it mEndToLenTotalLen.lower_bound(v[0]); if( mEndToLenTotalLen.end()! it) { lenShare min(it-second.first, it-first - v[0] 1); lenShare min(lenShare, v[2]); lenShare iTotalLen - it-second.second; } int iNeed v[2] - lenShare; if (iNeed 0) { continue; } iTotalLen iNeed; while(mEndToLenTotalLen.size()(v[1] - iNeed mEndToLenTotalLen.rbegin()-first)) { iNeed mEndToLenTotalLen.rbegin()-second.first; mEndToLenTotalLen.erase(std::prev(mEndToLenTotalLen.end())); } // std::cout v[1] iNeed std::endl; mEndToLenTotalLen.emplace(v[1], std::make_pair(iNeed, iTotalLen)); } return iTotalLen; } };
2023年第一版
class Solution { public: int findMinimumTime(vectorvector tasks) { std::sort(tasks.begin(), tasks.end(), [](const vector v1, const vector v2) { return v1[1] v2[1]; }); const int iMaxDay tasks.back()[1]; vector vWork(iMaxDay 1); int iRet 0; for (const auto v : tasks) { int iNeedWork v[2]; for (int i v[0]; i v[1]; i) { if (vWork[i]) { iNeedWork–; } } for (int i v[1]; iNeedWork 0; i–) { if (!vWork[i]) { vWork[i] true; iNeedWork–; iRet; } } } return iRet; } };
2023年第二版 class Solution {public:int findMinimumTime(vectorvectorint tasks) {std::sort(tasks.begin(), tasks.end(), [](const vectorint v1, const vectorint v2){return v1[1] v2[1];});vectorstd::tupleint, int, int vBeginEndTotalWork;vBeginEndTotalWork.emplace_back(-2, -2, 0);for (const auto v : tasks){int iNeedWork v[2];auto it std::lower_bound(vBeginEndTotalWork.begin(), vBeginEndTotalWork.end(), v[0], [](const std::tupleint, int, int t, const int i){return std::get0(t) i;});--it;iNeedWork - std::get2(vBeginEndTotalWork.back()) - std::get2(*it);if (v[0] std::get1(*it)){iNeedWork - std::get1(*it) - v[0] 1;}if (iNeedWork 0){continue;}while (v[1] - std::get1(vBeginEndTotalWork.back()) iNeedWork){iNeedWork (std::get1(vBeginEndTotalWork.back()) - std::get0(vBeginEndTotalWork.back()) 1);vBeginEndTotalWork.pop_back();}vBeginEndTotalWork.emplace_back(v[1] - iNeedWork 1, v[1], std::get2(vBeginEndTotalWork.back())iNeedWork);}return std::get2(vBeginEndTotalWork.back());}};扩展阅读
视频课程
有效学习明确的目标 及时的反馈 拉伸区难度合适可以先学简单的课程请移步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 C17 或者 操作系统win10 开发环境 VS2022 C17 如无特殊说明本算法用**C**实现。
