C++动态规划算法:最多可以参加的会议数目
本周推荐阅读
C++二分算法:得到子序列的最少操作次数
本题的其它解法
C++二分算法:最多可以参加的会议数目 II
本文涉及的基础知识点
二分查找算法合集
题目
给你一个 events 数组,其中 events[i] = [startDayi, endDayi, valuei] ,表示第 i 个会议在 startDayi 天开始,第 endDayi 天结束,如果你参加这个会议,你能得到价值 valuei 。同时给你一个整数 k 表示你能参加的最多会议数目。
你同一时间只能参加一个会议。如果你选择参加某个会议,那么你必须 完整 地参加完这个会议。会议结束日期是包含在会议内的,也就是说你不能同时参加一个开始日期与另一个结束日期相同的两个会议。
请你返回能得到的会议价值 最大和 。
示例 1:
输入:events = [[1,2,4],[3,4,3],[2,3,1]], k = 2
输出:7
解释:选择绿色的活动会议 0 和 1,得到总价值和为 4 + 3 = 7 。
示例 2:
输入:events = [[1,2,4],[3,4,3],[2,3,10]], k = 2
输出:10
解释:参加会议 2 ,得到价值和为 10 。
你没法再参加别的会议了,因为跟会议 2 有重叠。你 不 需要参加满 k 个会议。
示例 3:
输入:events = [[1,1,1],[2,2,2],[3,3,3],[4,4,4]], k = 3
输出:9
解释:尽管会议互不重叠,你只能参加 3 个会议,所以选择价值最大的 3 个会议。
**参数范围:
1 <= k <= events.length
1 <= k * events.length <= 106
1 <= startDayi <= endDayi <= 109
1 <= valuei <= 106
分析
上面的代码可以通过,也好理解。就是不够简洁,值转索引用了大约10行。直接先按结束时间排序,然后二分查找。
变量解释
vEndIndexNumToMaxValue[i][k]=j表示,event[0,i][1]结束,完成k个会议的最大价值。假定event[0,j)的结束时间都小于当前开始时间,event[j…)的结束时间都大于或等于当前开始时间。分两种情况:
| 0==j | 只能完成本任务 |
| j>0 | 参加会议j后,再参加任务i |
| 注意 | 确保vEndIndexNumToMaxValue[i][k]大于等于vEndIndexNumToMaxValue[i-1][k],否则就不递增了。递增才能进行二分查找 |
代码
错误代码一
class Solution {
public:
int maxValue(vector<vector>& events, const int K) {
m_c = events.size();
sort(events.begin(), events.end(), [](const auto& v1, const auto& v2) {return v1[1] < v2[1]; });
vector<vector> vEndIndexNumToMaxValue(m_c,vector(K + 1));
int iPreIndex = 0;
for (int i = 0 ; i < m_c ; i++ )
{
const auto& v = events[i];
while ((iPreIndex < m_c) && (events[iPreIndex][1] < v[0]))
{
iPreIndex++;
}
if (0 == iPreIndex)
{
vEndIndexNumToMaxValue[i].assign(K + 1, v[2]);
vEndIndexNumToMaxValue[i][0] = 0;
continue;
}
for (int k = 1; k <= K; k++)
{
vEndIndexNumToMaxValue[i][k] = max(vEndIndexNumToMaxValue[iPreIndex-1][k-1]+v[2],(0==i)?0:vEndIndexNumToMaxValue[i-1][k]);
}
}
return vEndIndexNumToMaxValue.back().back();
}
int m_c;
};
错误原因
必须确保vEndIndexNumToMaxValue,k相同时,递增。
注意:
vEndIndexNumToMaxValue[i][0] = 0;
错误代码二
class Solution {
public:
int maxValue(vector<vector>& events, const int K) {
m_c = events.size();
sort(events.begin(), events.end(), [](const auto& v1, const auto& v2) {return v1[1] < v2[1]; });
vector<vector> vEndIndexNumToMaxValue(m_c,vector(K + 1));
int iPreIndex = 0;
for (int i = 0 ; i < m_c ; i++ )
{
const auto& v = events[i];
while ((iPreIndex < m_c) && (events[iPreIndex][1] < v[0]))
{
iPreIndex++;
}
for (int k = 1; k <= K; k++)
{
const int iPreMax = (0 == iPreIndex) ? 0 : vEndIndexNumToMaxValue[iPreIndex - 1][k - 1];
vEndIndexNumToMaxValue[i][k] = max(iPreMax +v[2],(0==i)?0:vEndIndexNumToMaxValue[i-1][k]);
}
}
return vEndIndexNumToMaxValue.back().back();
}
int m_c;
};
错误原因
开始时间并不是递增的。
正确代码
class Solution {
public:int maxValue(vector<vector<int>>& events, const int K) {m_c = events.size();sort(events.begin(), events.end(), [](const auto& v1, const auto& v2) {return v1[1] < v2[1]; });vector<vector<int>> vEndIndexNumToMaxValue(m_c,vector<int>(K + 1));for (int i = 0 ; i < m_c ; i++ ){const auto& v = events[i];auto it = std::lower_bound(events.begin(), events.end(), v[0], [](const auto& v, int i) {return v[1] < i; });const int iLowerIndex = it - events.begin(); for (int k = 1; k <= K; k++){const int iPreMax = (0 == iLowerIndex) ? 0 : vEndIndexNumToMaxValue[iLowerIndex - 1][k - 1];vEndIndexNumToMaxValue[i][k] = max(iPreMax +v[2],(0==i)?0:vEndIndexNumToMaxValue[i-1][k]);} } return vEndIndexNumToMaxValue.back().back();}int m_c;
};
测试用例
template
void Assert(const T& t1, const T& t2)
{
assert(t1 == t2);
}
template
void Assert(const vector& v1, const vector& v2)
{
if (v1.size() != v2.size())
{
assert(false);
return;
}
for (int i = 0; i < v1.size(); i++)
{
Assert(v1[i], v2[i]);
}
}
int main()
{
vector<vector> events;
int k;
int res;
{
Solution slu;
events = { {53, 55, 77},{37, 56, 58} };
k = 1;
res = slu.maxValue(events, k);
Assert(res, 77);
}
{
Solution slu;
events = { {1,2,4},{3,4,3},{2,3,1} };
k = 2;
res = slu.maxValue(events, k);
Assert(res, 7);
}
{
Solution slu;
events = { {1,2,4},{3,4,3},{2,3,10} };
k = 2;
res = slu.maxValue(events, k);
Assert(res, 10);
}
{
Solution slu;
events = { {1,1,1},{2,2,2},{3,3,3},{4,4,4} };
k = 3;
res = slu.maxValue(events, k);
Assert(res, 9);
}
{
Solution slu;
events = { {21,77,43},{2,74,47},{6,59,22},{47,47,38},{13,74,57},{27,55,27},{8,15,8} };
k = 4;
res = slu.maxValue(events, k);
Assert(res, 57);
}
//CConsole::Out(res);
}
扩展阅读
视频课程
有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步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
| 我想对大家说的话 |
|---|
| 闻缺陷则喜是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。 |
| 子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙,那算法就是他的是睛 |
相关文章:
C++动态规划算法:最多可以参加的会议数目
本周推荐阅读 C二分算法:得到子序列的最少操作次数 本题的其它解法 C二分算法:最多可以参加的会议数目 II 本文涉及的基础知识点 二分查找算法合集 题目 给你一个 events 数组,其中 events[i] [startDayi, endDayi, valuei] …...
Windows 下安装MySQL8.0 Zip
1、将下载的mysql 压缩包解压。 2、已管理员身份证 打开 cmd窗口,进入到解压目录的,本文以解压到 D:\soft\mysql-8.0.29-winx64 为例来介绍。 3、在解压目录下 新建一个 my.ini 文件。 my.ini 文件内容如下: [mysqld] # 设置3306端口 por…...
8.2 Windows驱动开发:内核解锁与强删文件
在某些时候我们的系统中会出现一些无法被正常删除的文件,如果想要强制删除则需要在驱动层面对其进行解锁后才可删掉,而所谓的解锁其实就是释放掉文件描述符(句柄表)占用,文件解锁的核心原理是通过调用ObSetHandleAttri…...
【Spark源码分析】事件总线机制分析
Spark事件总线机制 采用Spark2.11源码,以下类或方法被DeveloperApi注解额部分,可能出现不同版本不同实现的情况。 Spark中的事件总线用于接受事件并提交到对应的监听器中。事件总线在Spark应用启动时,会在SparkContext中激活spark运行的事件总…...
c语言第七弹--扫雷小游戏!
今天做一个有趣的扫雷小游戏 现在正式开始设计。 思路:想要根本上实现必须拥有 实现函数的主体.c文件 头文件.h 及头文件实现.c。 头文件.h #pragma once #include <stdio.h> #include <stdlib.h> #include <time.h> #define EASY_COUNT 10 #d…...
浏览器是什么
浏览器是什么 本文简要介绍浏览器的功能和组成。 浏览器(Web Browser)是一种用于访问和浏览互联网上的网页和资源的软件应用程序。它是用户与互联网交互的主要工具之一。 浏览器通过使用网络协议(如HTTP、HTTPS等)与远程服务器通…...
一文彻底看懂Python切片,Python切片理解与操作
1.什么是切片 切片是Python中一种用于操作序列类型(如列表、字符串和元组)的方法。它通过指定起始索引和结束索引来截取出序列的一部分,形成一个新的序列。切片是访问特定范围内的元素,就是一个Area。 说个笑话:切片不是切片,而是切片,但是又是切片。大家理解下呢(末…...
聊聊tomcat的connection-timeout
序 本文主要研究一下tomcat的connection-timeout ServerProperties.Tomcat org/springframework/boot/autoconfigure/web/ServerProperties.java public static class Tomcat {/*** Access log configuration.*/private final Accesslog accesslog new Accesslog();/*** Th…...
HCIA-RS基础:动态路由协议基础
摘要:本文介绍动态路由协议的基本概念,为后续动态路由协议原理课程提供基础和引入。主要讲解常见的动态路由协议、动态路由协议的分类,以及路由协议的功能和自治系统的概念。文章旨在优化标题吸引力,并通过详细的内容夯实读者对动…...
jQuery 第十一章(表单验证插件推荐)
文章目录 前言jValidateZebra FormjQuery.validValValidityValidForm BuilderForm ValidatorProgressionformvalidationjQuery Validation PluginjQuery Validation EnginejQuery ValidateValidarium后言 前言 hello world欢迎来到前端的新世界 😜当前文章系列专栏&…...
SSL握手失败的解决方案
一、SSL握手失败的原因: 1,证书过期:SSL证书有一个有效期限,如果证书过期,就会导致SSL握手失败。 2,证书不被信任:如果网站的SSL证书不被浏览器或操作系统信任,也会导致SSL握手失败…...
K8S客户端一 Rancher的安装
一 安装方式一 通过官网方式安装:官网 sudo docker run --privileged -d --restartunless-stopped -p 80:80 -p 443:443 rancher/rancher:stable访问服务器地址即可:http://192.168.52.128 修改语言 第一次安装会生成密码,查看密码步骤如下…...
websocket与node.js实现
什么是 websocket? websoket 是一种网络通信协议,基于 tcp 连接的全双工通信协议(客户端和服务器可以同时收发信息),值得注意的是他不基于 http 协议,websocket 只有在建立连接的时候使用到 http 协议进行…...
postpresql 查询某张表的字段名和字段类型
postpresql 查询某张表的字段名和字段类型 工作中第一次接触postpresql,接触到这么个需求,只是对sql有点了解,于是就网上查阅资料。得知通过系统表可以查询,设计到几张系统表:pg_class、pg_attrubute、information_sc…...
jetson NX部署Yolov8
一,事情起因,由于需要对无人机机载识别算法进行更新,所以需要对yolov8算法进行部署到边缘端。 二,环境安装 安装虚拟环境管理工具,这个根据个人喜好。 我们需要选择能够在ARM架构上运行的conda,这里我们选择conda-forge 下载地址 安装即可 剩下的就是和conda 创建虚拟…...
【论文阅读笔记】Emu Edit: Precise Image Editing via Recognition and Generation Tasks
【论文阅读笔记】Emu Edit: Precise Image Editing via Recognition and Generation Tasks 论文阅读笔记论文信息摘要背景方法结果额外 关键发现作者动机相关工作1. 使用输入和编辑图像的对齐和详细描述来执行特定的编辑2. 另一类图像编辑模型采用输入掩码作为附加输入 。3. 为…...
python:列表的拷贝详解
python:列表的拷贝详解 文章目录 python:列表的拷贝详解方法1:直接赋值()方法2:浅拷贝(.copy方法)格式原理注意 方法3:深拷贝(.deepcopy方法)格式…...
zip4j压缩使用总结
一、引入依赖 <dependency><groupId>net.lingala.zip4j</groupId><artifactId>zip4j</artifactId><version>1.3.1</version></dependency>二、使用添加文件(addFiles)的方式生成压缩包 /*** Author wan…...
【第一部分:概述】ARM Realm Management Monitor specification
目录 概述机密计算系统软件组成MonitorRealmRealm Management Monitor (RMM)Virtual Machine (VM)HypervisorSecure Partition Manager (SPM)Trusted OS (TOS)Trusted Application (TA) Realm Management Monitor 参考文献 概述 RMM是一个软件组件,它构成了实现ARM…...
切换服务器上自己用户目录下的 conda 环境和一个外部的 Conda 环境
如果我们有自己的 Miniconda 安装和一个外部的 Conda 环境(比如一个全局安装的 Anaconda),我们可以通过修改 shell 环境来切换使用它们。这通常涉及到更改 PATH 环境变量,以便指向你想要使用的 Conda 安装的可执行文件:…...
LabVIEW 强度图与强度图表
LabVIEW 中强度图(Intensity Graph)与强度图表(Intensity Chart)均可接收二维数组作为输入,用于二维数据色彩可视化,二者核心差异体现在前面板运行行为上。强度图单次刷新、仅显示当前一组数据࿰…...
Flink 1.14 SQL Client 集成 Hive 3.x 全流程踩坑与终极解决方案
Flink 1.14 SQL Client 集成 Hive 3.x 全流程踩坑与终极解决方案 当企业级数据平台需要同时处理实时流计算和历史批处理时,Flink与Hive的深度集成成为刚需。然而在实际部署中,特别是面对CDH/HDP等商业发行版的Hive 3.x环境时,版本兼容性和依赖…...
别再写错pyqtgraph实时绘图了!一个QTimer+setData搞定动态曲线(附完整代码)
PyQtGraph实时绘图性能优化:QTimer与setData的正确打开方式 第一次接触PyQtGraph时,我像大多数从Matplotlib转来的开发者一样,习惯性地在每次数据更新时重新绘制整个图表。直到程序卡顿到无法运行,才意识到自己掉进了性能陷阱。本…...
深入浅出:从硬件原理图到DTS节点,图解RK3588外挂WiFi/蓝牙模块的驱动适配流程
从电路图到内核配置:RK3588外设驱动的硬件映射实战 当我们拿到一块RK3588开发板时,那些密密麻麻的电路图符号和内核中的设备树配置之间,到底存在着怎样的联系?这个问题困扰着许多从软件转向硬件开发的工程师。本文将以WiFi/蓝牙模…...
模块化量子计算中的容错接口技术解析
1. 模块化量子计算与容错接口技术概述量子计算正从实验室走向实用化,但构建百万量子比特规模的单一量子处理器面临巨大挑战。模块化架构通过连接多个小型量子处理单元(QPU)来解决这一难题,而容错接口技术则是实现模块化量子计算的关键所在。在模块化量子…...
RWKV7-1.5B-world应用场景:中文教育APP集成——作文批改+英文翻译双功能
RWKV7-1.5B-world应用场景:中文教育APP集成——作文批改英文翻译双功能 1. 引言:轻量级双语模型的教育应用价值 在中文教育APP开发中,智能批改和双语翻译是两大核心需求。传统方案需要分别部署作文批改和翻译模型,不仅资源消耗大…...
从Kubernetes到Docker:看云原生技术如何成功‘跨越鸿沟’(给技术布道者的实战指南)
云原生技术布道实战:如何复制Kubernetes的成功跨越路径 当Docker在2013年横空出世时,开发者们突然发现容器技术不再只是谷歌等科技巨头的专利。短短几年后,Kubernetes从Google内部项目成长为云原生计算的基石。这两个标志性技术的成功绝非偶然…...
xilinx vivado cameralink图像接收与发送代码,最大支持并行速度100MH...
xilinx vivado cameralink图像接收与发送代码,最大支持并行速度100MHz,优于编解码接口芯片。 不利用解码与编码芯片,直接在FPGA内部进行接收解码和发送。1. 系统架构总览 1.1 设计背景与目标 本代码实现了一个完整的Camera Link接口解决方案…...
ExplorerPatcher深度解析:让Windows 11重获经典操作体验
ExplorerPatcher深度解析:让Windows 11重获经典操作体验 【免费下载链接】ExplorerPatcher This project aims to enhance the working environment on Windows 项目地址: https://gitcode.com/GitHub_Trending/ex/ExplorerPatcher ExplorerPatcher是一款功能…...
Qianfan-OCR实操手册:批量处理脚本编写与OCR结果去重/合并/校验逻辑
Qianfan-OCR实操手册:批量处理脚本编写与OCR结果去重/合并/校验逻辑 1. 项目概述 Qianfan-OCR是百度千帆推出的开源文档智能多模态模型,基于4B参数的端到端架构设计。相比传统OCR方案,它集成了文字识别、版面分析和文档理解三大核心功能&am…...
