【二分查找】【区间合并】LeetCode2589:完成所有任务的最少时间

作者推荐

【动态规划】【广度优先】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

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛