【二分查找】【区间合并】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

相关

下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

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

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。