作者推荐
【动态规划】【广度优先】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 | 已已有时间，本次任务能运行的时间。 |
| (get<0>(*it) - max(curBegin, v[0]) + 1) | 当前任务，it时间段能运行的时间 |
| curNotUse | it及之前的时间段，当前任务无法运行的时间。it后的时间段当前任务一定能运行。 |
| (v[1] - get<0>(vEndLenTotalLen.back()) <= iNeedAdd) | 新加的时间段，需要和之前的时间段合并么？ |
代码
核心代码
class Solution {
public:
int findMinimumTime(vector<vector<int>>& tasks) {
sort(tasks.begin(), tasks.end(), [](const auto& v1, const auto& v2) {return v1[1] < v2[1]; });
vector<tuple<int, 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 get<0>(t) < i; });
int iHasLen = 0;
if ((vEndLenTotalLen.end() != it))
{
const int curBegin = get<0>(*it) - get<1>(*it) + 1;
const int curNotUse = get<2>(*it) - (get<0>(*it) - max(curBegin, v[0]) + 1);
iHasLen = get<2>(vEndLenTotalLen.back()) - curNotUse;
}
int iNeedAdd = v[2] - iHasLen;
if (iNeedAdd <= 0 )
{
continue;
}
while (vEndLenTotalLen.size() && (v[1] - get<0>(vEndLenTotalLen.back()) <= iNeedAdd))
{
iNeedAdd += get<1>(vEndLenTotalLen.back());
vEndLenTotalLen.pop_back();
}
vEndLenTotalLen.emplace_back(v[1], iNeedAdd, iNeedAdd + (vEndLenTotalLen.empty() ? 0 : get<2>(vEndLenTotalLen.back())));
}
return get<2>(vEndLenTotalLen.back());
}
};
测试用例
template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
if (v1.size() != v2.size())
{
assert(false);
return;
}
for (int i = 0; i < v1.size(); i++)
{
assert(v1[i] == v2[i]);
}
}
template<class T>
void Assert(const T& t1, const T& t2)
{
assert(t1 == t2);
}
int main()
{
vector<vector<int>> 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(vector<vector>& tasks) {
sort(tasks.begin(), tasks.end(), [](const vector& v1, const vector& v2)
{
return v1[1] < v2[1];
});
std::multimap<int, pair<int, 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(vector<vector>& 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(vector<vector<int>>& tasks) {
std::sort(tasks.begin(), tasks.end(), [](const vector<int>& v1, const vector<int>& v2)
{
return v1[1] < v2[1];
});
vector<std::tuple<int, 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::tuple<int, int, int>& t, const int i)
{
return std::get<0>(t) < i;
});
--it;
iNeedWork -= std::get<2>(vBeginEndTotalWork.back()) - std::get<2>(*it);
if (v[0] <= std::get<1>(*it))
{
iNeedWork -= std::get<1>(*it) - v[0] + 1;
}
if (iNeedWork <= 0)
{
continue;
}
while (v[1] - std::get<1>(vBeginEndTotalWork.back()) <= iNeedWork)
{
iNeedWork += (std::get<1>(vBeginEndTotalWork.back()) - std::get<0>(vBeginEndTotalWork.back()) + 1);
vBeginEndTotalWork.pop_back();
}
vBeginEndTotalWork.emplace_back(v[1] - iNeedWork + 1, v[1], std::get<2>(vBeginEndTotalWork.back())+iNeedWork);
}
return std::get<2>(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 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
