作者推荐
本文涉及的基础知识点
二分查找算法合集 有序向量的二分查找，向量只会在尾部增加删除。
题目
你有一台电脑，它可以 同时 运行无数个任务。给你一个二维整数数组 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()); } };
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
