C++二分查找算法:规划兼职工作

题目

你打算利用空闲时间来做兼职工作赚些零花钱。
这里有 n 份兼职工作,每份工作预计从 startTime[i] 开始到 endTime[i] 结束,报酬为 profit[i]。
给你一份兼职工作表,包含开始时间 startTime,结束时间 endTime 和预计报酬 profit 三个数组,请你计算并返回可以获得的最大报酬。
注意,时间上出现重叠的 2 份工作不能同时进行。
如果你选择的工作在时间 X 结束,那么你可以立刻进行在时间 X 开始的下一份工作。
示例 1:
输入:startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]
输出:120
解释:
我们选出第 1 份和第 4 份工作,
时间范围是 [1-3]+[3-6],共获得报酬 120 = 50 + 70。
示例 2:
输入:startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,70,60]
输出:150
解释:
我们选择第 1,4,5 份工作。
共获得报酬 150 = 20 + 70 + 60。
示例 3:
输入:startTime = [1,1,1], endTime = [2,3,4], profit = [5,6,4]
输出:6
参数范围
1 <= startTime.length == endTime.length == profit.length <= 5 * 10^4
1 <= startTime[i] < endTime[i] <= 10^9
1 <= profit[i] <= 10^4

分析

基础分析

假定先完成工作i,再完成j,那么start[i]一定小于start[j],所以先对开始时间排序。证明:startTime[i] < endTime[i] 且endTime[i] <=startTime[j]。只排序索引就可以了。
mEndTimeToProfit的key对应已完成工作的时间,value对应总报酬。如果key0 <=key1,且value0 >= value1,则key2被淘汰。
key1能被选择,key0一定能被选择,且value0大于等于value1。淘汰后,键key和值value都是按升序排序。
由于必定有结果,所以无需判断mEndTimeToProfit是否为空,由于值也是升序,所以返回最后一个元素。

时间复杂度

O(nlogn)。至少能完成一份工作,我们枚举最后一份工作。

如果没有工作已经结束则只能完成本工作
如果有工作已完成完成本工作+已经完成工作中报酬最多的工作

代码

template<class _Kty,class _Ty,bool bValueDdes,bool bOutSmallKey>
class COrderValueMap
{
public:
void Add (_Kty iValue, _Ty iNum)
{
if (!bOutSmallKey)
{
if (bValueDdes)
{
Add(iValue, iNum, std::greater_equal<_Ty>(), std::less_equal<_Ty>());
}
else
{
Add(iValue, iNum, std::less_equal<_Ty>(), std::greater_equal<_Ty>());
}
}
};
template<class _Pr1, class _Pr2>
void Add(_Kty iValue, _Ty iNum, _Pr1 pr1,_Pr2 pr2 )
{
if (!bOutSmallKey)
{
auto it = m_map.upper_bound(iValue);
if ((m_map.begin() != it) && pr1(std::prev(it)->second ,iNum))
{
return;//被淘汰
}
auto ij = it;
for (; (m_map.end() != ij) && pr2(ij->second , iNum); ++ij);
m_map.erase(it, ij);
m_map[iValue] = iNum;
}
};
std::map<_Kty, _Ty> m_map;
};

class Solution {
public:
int jobScheduling(vector& startTime, vector& endTime, vector& profit) {
m_c = startTime.size();
vector indexs;
for (int i = 0; i < m_c; i++)
{
indexs.emplace_back(i);
}
sort(indexs.begin(), indexs.end(), [&startTime](const int& i1, const int& i2) {return startTime[i1] < startTime[i2]; });
COrderValueMap<int,int,true,false> mEndTimeToProfit;
for (int i : indexs)
{
auto it = mEndTimeToProfit.m_map.upper_bound(startTime[i]);
int iTotalProfit = profit[i];
if (mEndTimeToProfit.m_map.begin() != it)
{
iTotalProfit += std::prev(it)->second;
}
mEndTimeToProfit.Add(endTime[i], iTotalProfit);
}
return mEndTimeToProfit.m_map.rbegin()->second;
}
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 startTime, endTime, profit;
int res;
{
Solution slu;
startTime = { 1, 2, 3, 3 };
endTime = { 3, 4, 5, 6 };
profit = { 50, 10, 40, 70 };
res = slu.jobScheduling(startTime, endTime, profit);
Assert(120, res);
}

//CConsole::Out(res);

}

2023年一月旧代码

class Solution {
public:
int jobScheduling(vector& startTime, vector& endTime, vector& profit) {
m_c = startTime.size();
vector indexs;
for (int i = 0; i < m_c; i++)
{
indexs.push_back(i);
}
std::sort(indexs.begin(), indexs.end(), [&startTime](const int& i1, const int& i2)
{
return startTime[i1] < startTime[i2];
});
int iMaxProfit = 0;
std::map<int, int> mEndProfit;
for (int i = 0; i < indexs.size(); i++ )
{
const int& index = indexs[i];
const int iNewEnd = endTime[index];
const int iProfit = iMaxProfit + profit[index];
if (mEndProfit.count(iNewEnd))
{
mEndProfit[iNewEnd] = max(mEndProfit[iNewEnd], iProfit);
}
else
{
mEndProfit[iNewEnd] = iProfit;
}
if (i + 1 < indexs.size())
{
const int iNextStart = startTime[indexs[i + 1]];
while (mEndProfit.size() && (mEndProfit.begin()->first <= iNextStart))
{
iMaxProfit = max(iMaxProfit, mEndProfit.begin()->second);
mEndProfit.erase(mEndProfit.begin());
}
}
}
for (auto& it : mEndProfit)
{
iMaxProfit = max(iMaxProfit, it.second);
}
return iMaxProfit;
}
int m_c;
};

2023年8月旧代码

class Solution {
public:
int jobScheduling(vector& startTime, vector& endTime, vector& profit) {
m_c = startTime.size();
vector indexs(m_c);
iota(indexs.begin(), indexs.end(), 0);
sort(indexs.begin(), indexs.end(), [&](const int i1, const int i2)
{
return startTime[i1] < startTime[i2];
});
std::map<int, int> mEndTotalPro;
int iMaxPro = 0;
for (int i : indexs)
{
while (mEndTotalPro.size() && (mEndTotalPro.begin()->first <= startTime[i]))
{
iMaxPro = max(iMaxPro, mEndTotalPro.begin()->second);
mEndTotalPro.erase(mEndTotalPro.begin());
}
const int end = endTime[i];
mEndTotalPro[end] = max(mEndTotalPro[end], profit[i] + iMaxPro);
}
int iRet = 0;
for (const auto& it : mEndTotalPro)
{
iRet = max(iRet, it.second);
}
return iRet;
}
int m_c;
};

扩展阅读

视频课程

有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步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

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

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

相关文章

Vue3 生命周期

如下是Vue3的生命周期函数图&#xff1a; 一、Vue2生命周期和Vue3声明周期的区别 1. Vue2 中&#xff0c;只要创建Vue实例对象而不需要挂载就可以实现beforeCreate 和 created 生命周期函数。 Vue3中必须要将Vue实例对象挂载完成&#xff0c;所有的准备工作做完&#xff0c;…

V10 桌面版、服务器版系统加固

V10 桌面版、服务器版系统加固 一、 文档说明 本文档中涉及的加固方法主要包括&#xff1a;密码策略配置、防火墙规 则配置、禁用高风险服务等。 二、 V10 桌面版系统加固 2.1 密码策略配置 密码策略包括密码老化控制策略和密码复杂度策略。密码老化 控制策略需要配置/etc…

Git客户端(TortoiseGit)使用

参考文章&#xff1a; https://www.cnblogs.com/xuwenjin/p/8573603.html 【精选】使用TortoiseGit工具进行开发&#xff08;连接远程仓库进行克隆、拉取、获取、提交、推送、新建/切换/合并分支、解决冲突&#xff09;_tortoisegit连接远程仓库-CSDN博客 tortoise git 拉取…

二进制的形式在内存中绘制一个对象实例

一、引用类型实例的内存布局 从内存布局的角度来看&#xff0c;一个引用类型的实例由如下图所示的三部分组成&#xff1a;ObjHeader TypeHandle Fields。前置的ObjHeader用来缓存哈希值和同步状态&#xff0c;TypeHandle部分存储类型对应方法表&#xff08;Method Table&…

2023.11.17 -hivesql调优,数据压缩,数据存储

目录 1.hive命令和参数配置 2.hive数据压缩 3.hive数据存储 0.原文件大小 18.1MB 1.textfile行存储格式, 压缩后size:18MB 2.行存储格式:squencefile ,压缩后大小8.89MB​ 3. 列存储格式 orc - ZILIB ,压缩后大小2.78MB 4.列存储格式 orc-snappy ,压缩后大小3.75MB 5…

设计模式-中介者模式-笔记

Medicator中介者模式 动机&#xff08;Motivation&#xff09; 在软件构建过程中&#xff0c;经常会出现多个对象相互关联交际的情况&#xff0c;对象之间常常会维持一种复杂的引用关系&#xff0c;如果遇到一些需求的更改&#xff0c;这种直接的引用关系将面临不断的变化。 …

简单回顾矩阵的相乘(点乘)230101

[[1 0 1][1 1 0]] [[3 0 0 3][2 2 1 3][1 3 1 1]] [[4. 3. 1. 4.][5. 2. 1. 6.]]乘以 c11 a11*b11 a12*b21 a13*b31 1*3 0*2 1*1 4 c12 a11*b12 a12*b22 a13*b32 1*0 0*2 1*3 3 c13a11*b13 a12*b23a13*b33 c14a11*b14 a12*b24a13*b34 c21a21*b11 a22*b21 a23*b…

【iDRAC】突破错误信息壁垒,利用iDRAC提高效率

序 面对旧服务器上的黄色警示灯&#xff0c;工作人员往往陷入困惑。更糟糕的是&#xff0c;如果该服务器转手多次&#xff0c;缺少root用户密码和IP地址&#xff0c;那么要访问服务器iDRAC就更困难了。但是出现问题的硬件蕴含着重要信息&#xff0c;为了解开这个谜团&#xff…

基于STC12C5A60S2系列1T 8051单片的IIC总线器件数模芯片PCF8591实现数模转换应用

基于STC12C5A60S2系列1T 8051单片的IIC总线器件数模芯片PCF8591实现数模转换应用 STC12C5A60S2系列1T 8051单片机管脚图STC12C5A60S2系列1T 8051单片机I/O口各种不同工作模式及配置STC12C5A60S2系列1T 8051单片机I/O口各种不同工作模式介绍IIC总线器件数模芯片PCF8591介绍通过按…

windows11编译ffmpeg

安装msys2&#xff0c;直接https://www.msys2.org/上下载exe安装即可&#xff0c;默认路径&#xff1b; 选择msys2-mingw64启动&#xff0c;将下载源替换为中科大 sed -i "s#mirror.msys2.org/#mirrors.ustc.edu.cn/msys2/#g" /etc/pacman.d/mirrorlist*pacman -S…

RocketMQ的适用场景有哪些?

程序员的公众号&#xff1a;源1024&#xff0c;获取更多资料&#xff0c;无加密无套路&#xff01; 最近整理了一波电子书籍资料&#xff0c;包含《Effective Java中文版 第2版》《深入JAVA虚拟机》&#xff0c;《重构改善既有代码设计》&#xff0c;《MySQL高性能-第3版》&…

Leetcode刷题详解——衣橱整理

1. 题目链接&#xff1a;LCR 130. 衣橱整理 2. 题目描述&#xff1a; 家居整理师将待整理衣橱划分为 m x n 的二维矩阵 grid&#xff0c;其中 grid[i][j] 代表一个需要整理的格子。整理师自 grid[0][0] 开始 逐行逐列 地整理每个格子。 整理规则为&#xff1a;在整理过程中&am…

解决:Android TextView 设置斜体后右侧文字被遮挡

一、问题说明 遇到一个比较奇怪的情况&#xff0c;给 TextView 文字设置倾斜后&#xff0c;右侧的文字会被遮挡&#xff0c;感觉这应该是 Android 的一个 bug &#xff01; 上代码&#xff1a; <TextViewandroid:id"id/tv_title"android:layout_width"wra…

【计算机网络笔记】网络地址转换(NAT)

系列文章目录 什么是计算机网络&#xff1f; 什么是网络协议&#xff1f; 计算机网络的结构 数据交换之电路交换 数据交换之报文交换和分组交换 分组交换 vs 电路交换 计算机网络性能&#xff08;1&#xff09;——速率、带宽、延迟 计算机网络性能&#xff08;2&#xff09;…

GO语言的由来与发展历程

Go语言&#xff0c;也称为Golang&#xff0c;是由Google公司的Robert Griesemer、Ken Thompson和Rob Pike三个大牛于2007年开始设计发明&#xff0c;并于2009年正式对外发布的开源编程语言。 三名初始人的目标是设计一种适应网络和多核时代的C语言&#xff0c;Go语言从C继承了…

Rust 语言中的结构体

目录 1、结构体 2、结构体的定义和实例化 2.1 使用字段初始化简写语法 2.2 使用结构体更新语法从其他实例创建实例 2.3 没有命名字段的元组结构体 2.4 没有任何字段的类单元结构体 2.5 结构体示例程序 3、方法 3.1 关联函数 3.2 多个 impl 块 1、结构体 struct&…

2023年09月 Python(六级)真题解析#中国电子学会#全国青少年软件编程等级考试

Python等级考试(1~6级)全部真题・点这里 一、单选题(共25题,每题2分,共50分) 第1题 以下选项中,不是tkinter变量类型的是?( ) A: IntVar() B: StringVar() C: DoubleVar() D: FloatVar() 答案:D tkinter 无 FloatVar()变量类型。 第2题 关于tkinter,以下说…

C++二分算法:使数组严格递增

涉及知识点 动态规划 二分查找 题目 给你两个整数数组 arr1 和 arr2&#xff0c;返回使 arr1 严格递增所需要的最小「操作」数&#xff08;可能为 0&#xff09;。 每一步「操作」中&#xff0c;你可以分别从 arr1 和 arr2 中各选出一个索引&#xff0c;分别为 i 和 j&#…

OceanBase:中国场景推动树立分布式数据库四项新标准

11月16日&#xff0c;在OceanBase2023年度发布会上&#xff0c;OceanBase CEO杨冰介绍&#xff0c;中国数字经济的蓬勃发展催生了对分布式数据库的强大需求&#xff0c;这种需求也牵引了OceanBase坚定投入自主研发&#xff0c;从而推动树立了分布式数据库的四项新标准。 据了解…

【计算机组成原理】定点加法、减法运算

系列文章目录 绘制出纯整数(1字节)和纯小数的数轴 将十进制数20.59375&#xff0c;转换成754标准的32位浮点数的二进制存储格式 用双符号位补码求 x 0.1010011, y -0.1001010, 分别求出 x y, x - y&#xff0c;并判溢出