【二分查找】【区间合并】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时间段能运行的时间
curNotUseit及之前的时间段，当前任务无法运行的时间。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++**实现。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/240786.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

万界星空科技MES系统中的生产调度流程

万界星空科技MES系统中的生产调度流程

MES系统生产调度的目标是达到作业有序、协调、可控和高效的运行效果&#xff0c;作业计划的快速生成以及面向生产扰动事件的快速响应处理是生产调度系统的核心和关键。 为了顺利生成作业计划&#xff0c;需要为调度系统提供完整的产品和工艺信息&#xff0c;MES系统生成作业计…
阅读更多...
Flutter打包iOS苹果IPA应用有哪些优势？如何实现？

Flutter打包iOS苹果IPA应用有哪些优势？如何实现？

Hello各位小伙伴们各位开发者们好&#xff0c;我是咕噜铁蛋&#xff01;&#xff0c;经常和移动应用开发相关的话题打交道的伙伴们都知道。在开发移动应用时&#xff0c;选择合适的打包方式对于应用的发布和分发至关重要。在今天这篇文章中&#xff0c;我将和大家聊聊Flutter打…
阅读更多...
【小沐学Python】Python实现语音识别（Whisper）

【小沐学Python】Python实现语音识别（Whisper）

文章目录 1、简介1.1 whisper简介1.2 whisper模型 2、安装2.1 whisper2.2 pytorch2.3 ffmpeg 3、测试3.1 命令测试3.2 代码测试&#xff1a;识别声音文件3.3 代码测试&#xff1a;实时录音识别 4、工具4.1 WhisperDesktop4.2 Buzz4.3 Whisper-WebUI 结语 1、简介 https://gith…
阅读更多...
基于QTreeWidget实现多级组织结构

基于QTreeWidget实现多级组织结构

基于QTreeWidget实现多级组织结构以及带Checkbox的选择树 采用基于QWidgetMingw实现的原生的消息气泡 通过QTreeWidget控件实现的多级组织结构树。 基于QTreeWidget实现多级组织结构代码已上传到【https://gitee.com/duyanjun/bubbleChat.git】 目录 基于QTreeWidget实现多级组…
阅读更多...
浅谈微服务架构的演进

浅谈微服务架构的演进

本文将介绍微服务架构和相关的组件&#xff0c;介绍他们是什么以及为什么要使用微服务架构和这些组件。本文侧重于简明地表达微服务架构的全局图景&#xff0c;因此不会涉及具体如何使用组件等细节。 要理解微服务&#xff0c;首先要先理解不是微服务的那些。通常跟微服务相对…
阅读更多...
Redis系列之简单实现watchDog自动续期机制

Redis系列之简单实现watchDog自动续期机制

在分布锁的实际使用中&#xff0c;可能会遇到一种情况&#xff0c;一个业务执行时间很长&#xff0c;已经超过redis加锁的时间&#xff0c;也就是锁已经释放了&#xff0c;但是业务还没执行完成&#xff0c;这时候其它线程还是可以获取锁&#xff0c;那就没保证线程安全 项目环…
阅读更多...
【Unity学习笔记】光照简介

【Unity学习笔记】光照简介

本节主要是简单介绍一些常见的光照组件和渲染设置。 文章目录 灯光类型平行光Directional Light点光源Point Light聚光灯Spot Light面积光 Area Light 阴影设置全局光照明光照模式直接光照与间接光照Mixed Lighting 光照探针Light Probe Group光照探针组 反射探针 灯光类型 在…
阅读更多...
使用 Python 实现简单的爬虫框架

使用 Python 实现简单的爬虫框架

爬虫是一种自动获取网页内容的程序&#xff0c;它可以帮助我们从网络上快速收集大量信息。在本文中&#xff0c;我们将学习如何使用 Python 编写一个简单的爬虫框架。 一、请求网页 首先&#xff0c;我们需要请求网页内容。我们可以使用 Python 的 requests 库来发送 HTTP 请…
阅读更多...
CLEAR MOT评估指标

CLEAR MOT评估指标

错误正样本&#xff08;False Positive&#xff0c;FP&#xff09;&#xff1a;整个视频中被预测为正的负样本数。 错误负样本&#xff08;False Negatives&#xff0c;FN&#xff09;&#xff1a;整个视频中被预测为负的正样本数。 IDs&#xff1a;跟踪过程中目标ID切换总数。…
阅读更多...
springcloud微服务篇--2.微服务之间的调用

springcloud微服务篇--2.微服务之间的调用

一、微服务案例需求1&#xff1a; 根据订单id查询订单的同时&#xff0c;把订单所属的用户信息一起返回 1、新建订单项目&#xff0c;用户服务。 2.RestTemplate实现微服务之间的访问。 在order-service的OrderApplication中注册RestTemplate 注入调用&#xff1a; Autowire…
阅读更多...
【ModBus进阶日记】①ModBus协议栈解析

【ModBus进阶日记】①ModBus协议栈解析

关注星标公众号&#xff0c;不错过精彩内容 文章目录 前言一、ModBus简介二、ModBus协议概述2.1 ModBus RTU主机框架2.2 ModBus RTU从机框架 三、ModBus帧描述四、ModBus RTU模式的报文断帧五、ModBus字节序六、ModBus事务处理流程七、ModBus异常响应八、ModBus功能码定义九、…
阅读更多...
如何实现nacos的配置的热更新

如何实现nacos的配置的热更新

我们在使用nacos进行修改配置后&#xff0c;需要微服务无需重启即可让配置生效&#xff0c;也就是使配置进行热更新我们可以采用下面的两种方式进行配置的热更新操作 方式一&#xff1a;在Value所注入的变量的类上添加注解RefreshScope RestController RequestMapping("/o…
阅读更多...
Local Color Distributions Prior for ImageEnhancement

Local Color Distributions Prior for ImageEnhancement

图1&#xff1a;给定同时具有过曝光&#xff08;背景窗口&#xff09;和欠曝光&#xff08;前景人物&#xff09;的输入图像&#xff08;a&#xff09;&#xff0c;现有方法不能很好地处理这两个问题。虽然&#xff08;b&#xff09;在背景上表现更好&#xff0c;但前景仅略微变…
阅读更多...
anolisos8.8安装显卡+CUDA工具+容器运行时支持（containerd/docker）+k8s部署GPU插件

anolisos8.8安装显卡+CUDA工具+容器运行时支持（containerd/docker）+k8s部署GPU插件

anolisos8.8安装显卡及cuda工具 一、目录 1、测试环境 2、安装显卡驱动 3、安装cuda工具 4、配置容器运行时 5、K8S集群安装nvidia插件 二、测试环境 操作系统&#xff1a;Anolis OS 8.8 内核版本&#xff1a;5.10.134-13.an8.x86_64 显卡安装版本&#xff1a;525.147.05 c…
阅读更多...
学习笔记——GDB调试器

学习笔记——GDB调试器

感谢B站up主 xiaobing1016 的学习视频&#xff1a;基于VSCode和CMake实现C/C开发 | Linux篇_哔哩哔哩_bilibili
阅读更多...
电脑加密软件哪个最好用（电脑加密软件排行榜2023）

电脑加密软件哪个最好用（电脑加密软件排行榜2023）

你公司的电脑数据在裸奔&#xff1f; 你公司的核心文件完全开放&#xff1f; 你公司的机密图纸谁都能获取&#xff1f; …… 作为老板的你&#xff0c;该不会还不知道电脑加密软件能够解决上述这些问题吧&#xff01; 我看过一个案例&#xff0c;新闻报道的略显夸张&#x…
阅读更多...
企业资产管理技巧，这一点厉害了！

企业资产管理技巧，这一点厉害了！

​随着市场竞争的不断加剧和金融环境的日益复杂&#xff0c;有效地管理和优化资产已经成为保持竞争优势和实现财务目标的不可或缺的一环。资产不仅仅是组织或个人的财富&#xff0c;更是潜在的增长动力和风险源。 传统的资产管理方法已经不再适应现代快速变化的经济环境。为了适…
阅读更多...
【C语言程序设计】选择结构程序设计

【C语言程序设计】选择结构程序设计

目录 前言 一、程序阅读 二、程序改错 三、程序设计 总结 &#x1f308;嗨&#xff01;我是Filotimo__&#x1f308;。很高兴与大家相识&#xff0c;希望我的博客能对你有所帮助。 &#x1f4a1;本文由Filotimo__✍️原创&#xff0c;首发于CSDN&#x1f4da;。 &#x1f4e3;如…
阅读更多...
时间序列预测 — CNN-LSTM实现多变量多步光伏预测(Tensorflow)

时间序列预测 — CNN-LSTM实现多变量多步光伏预测(Tensorflow)

目录 1 数据处理 1.1 导入库文件 1.2 导入数据集 1.3 缺失值分析 2 构造训练数据 ​3 模型训练 3.1 CNN-LSTM网络 3.2 模型训练 4 模型预测 专栏链接&#xff1a;https://blog.csdn.net/qq_41921826/category_12495091.html 1 数据处理 1.1 导入库文件 import scip…
阅读更多...
一些paper工具帮你搞定日常科研工作

一些paper工具帮你搞定日常科研工作

如果你是在校生&#xff0c;科研er 你的日常避免各种各样的pepers&#xff1b;找papers&#xff0c;读papers&#xff0c;写papers。这三部曲贯穿这你整个科研工作&#xff0c;如何在有限的时间里&#xff0c;能够高效的完成科研&#xff0c;且保质保量&#xff0c;我们需要一些…
阅读更多...
最新文章

Copyright @ 2022~2023