当前位置: 首页 > news >正文

Leetcode 1235. 规划兼职工作

1.题目基本信息

1.1.题目描述

你打算利用空闲时间来做兼职工作赚些零花钱。

这里有 n 份兼职工作,每份工作预计从 startTime[i] 开始到 endTime[i] 结束,报酬为 profit[i]。

给你一份兼职工作表,包含开始时间 startTime,结束时间 endTime 和预计报酬 profit 三个数组,请你计算并返回可以获得的最大报酬。

注意,时间上出现重叠的 2 份工作不能同时进行。

如果你选择的工作在时间 X 结束,那么你可以立刻进行在时间 X 开始的下一份工作。

1.2.题目地址

https://leetcode.cn/problems/maximum-profit-in-job-scheduling/description/

2.解题方法

2.1.解题思路

动态规划+二分查找

2.2.解题步骤

第一步,状态定义;dp[i]为前i个兼职工作的最大报酬

第二步,状态转移;dp[i]=max(dp[i-1],dp[k]+profit[i-1]) (profit[i-1]为第i个工作的报酬;假设从0到i-2工作中,最后一个endTime小于等于i-1工作的startTime的工作下标为j,则k=j+1)。这里使用左闭右闭的未标记区间的方式进行二分

3.解题代码

Python代码

class Solution:def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:length=len(startTime)jobs=sorted(zip(startTime,endTime,profit),key=lambda item:item[1])# 第一步,状态定义;dp[i]为前i个兼职工作的最大报酬dp=[0]*(length+1)# 第二步,状态转移;dp[i]=max(dp[i-1],dp[k]+profit[i-1]) (profit[i-1]为第i个工作的报酬;假设从0到i-2工作中,最后一个endTime小于等于i-1工作的startTime的工作下标为j,则k=j+1)。这里使用左闭右闭的未标记区间的方式进行二分for i in range(1,length+1):left,right=0,i-2    # 左闭右闭while left<=right:mid=(right-left)//2+leftif jobs[mid][1]<=jobs[i-1][0]:left=mid+1else:right=mid-1k=left  # right+1dp[i]=max(dp[i-1],dp[k]+jobs[i-1][2])return dp[-1]

C++代码

class Solution {
public:int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {int length=startTime.size();vector<vector<int>> jobs(length);for(int i=0;i<length;++i){jobs[i]={startTime[i],endTime[i],profit[i]};}sort(jobs.begin(),jobs.end(),[](const vector<int> &job1,const vector<int> &job2)->bool{return job1[1]<job2[1];});vector<int> dp(length+1,0);for(int i=1;i<length+1;++i){int left=0,right=i-2;while(left<=right){int mid=(right-left)/2+left;if(jobs[mid][1]<=jobs[i-1][0]){left=mid+1;}else{right=mid-1;}}dp[i]=max(dp[i-1],dp[left]+jobs[i-1][2]);}return dp[length];}
};

4.执行结果

在这里插入图片描述

相关文章:

Leetcode 1235. 规划兼职工作

1.题目基本信息 1.1.题目描述 你打算利用空闲时间来做兼职工作赚些零花钱。 这里有 n 份兼职工作&#xff0c;每份工作预计从 startTime[i] 开始到 endTime[i] 结束&#xff0c;报酬为 profit[i]。 给你一份兼职工作表&#xff0c;包含开始时间 startTime&#xff0c;结束时…...

LeetCode 2535.数组元素和与数字和的绝对差:模拟

【LetMeFly】2535.数组元素和与数字和的绝对差&#xff1a;模拟 力扣题目链接&#xff1a;https://leetcode.cn/problems/difference-between-element-sum-and-digit-sum-of-an-array/ 给你一个正整数数组 nums 。 元素和 是 nums 中的所有元素相加求和。数字和 是 nums 中每…...

SpringCloud-pom创建Eureka

<?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0" xmlns:xsi"http://www.w3.org/2001/XMLSchema-instance"xsi:schemaLocation"http://maven.apache.org/POM/4.0.0 https://…...

动态规划算法专题(一):斐波那契数列模型

目录 1、动态规划简介 2、算法实战应用【leetcode】 2.1 题一&#xff1a;第N个泰波那契数 2.1.1 算法原理 2.1.2 算法代码 2.1.3 空间优化原理——滚动数组 2.1.4 算法代码——空间优化版本 2.2 题二&#xff1a;三步问题 2.2.1 算法原理 2.2.2 算法代码 2.3 题二&a…...

H.264编解码工具 - x264

一、简介 x264是一个开源的H.264/AVC视频编码库,它可以将视频数据压缩成H.264格式,并且可以从H.264格式解码出原始视频数据。 x264是以C语言编写的,并且可以在多个平台上使用,包括Windows、Linux和Mac OS等操作系统。 x264具有很高的编码效率和视频质量,它支持多种编码…...

外卖点餐小程序源码系统 单店多门店自助切换 带完整的安装代码包以及搭建部署教程

系统概述 本外卖点餐小程序源码系统旨在帮助餐饮企业和商家快速搭建一个功能完善的在线外卖平台。系统支持单店与多门店的灵活切换&#xff0c;方便商家根据自身业务需求进行管理和运营。同时&#xff0c;系统还提供了丰富的营销工具和数据分析功能&#xff0c;助力商家实现精…...

通过Ideal和gitbash共同实现分支合并

文章目录 背景描述&#xff1a;演示jy_20240704_develop分支同步到jy_dev分支方式一方式二 背景描述&#xff1a; 目前项目里有四个分支&#xff0c;分别是master、jy_20240704_develop、jy_dev、jy_qas。 其中master是主分支&#xff0c;其他三个分支都是根据master来创建的…...

Vue.js 组件开发

Vue.js 是一个渐进式的JavaScript框架&#xff0c;主要用于构建用户界面。它采用了组件化的开发方式&#xff0c;使得前端开发更加高效、灵活且易于维护。组件是Vue.js的核心概念之一&#xff0c;理解和掌握组件的开发&#xff0c;有助于我们高效地构建现代Web应用。 本文将涵…...

【Lcode 随笔】C语言版看了不后悔系列持续更新中。。。

文章目录 题目一&#xff1a;最长回文子串题目描述&#xff1a;示例输入与输出&#xff1a;题目分析&#xff1a;解题思路&#xff1a;示例代码&#xff1a;深入剖析&#xff1a; 题目二&#xff1a;合并K个有序链表题目描述&#xff1a;示例输入与输出&#xff1a;题目分析&am…...

排序--希尔排序

希尔排序介绍 希尔排序核心思想就是:1,分组;2,直接插入排序:越有序越快 希尔排序就是多次利用直接插入排序的一个排序算法. 希尔排序的算法思想:间隔式分组,利用直接插入排序让组内有序,然后缩小分组再次排序,直到组数为1希尔排序的理论基础就是直接插入排序越有序越快; 希尔排…...

【教程】57帧! Mac电脑流畅运行黑神话悟空

转载请注明出处&#xff1a;小锋学长生活大爆炸[xfxuezhagn.cn] 如果本文帮助到了你&#xff0c;欢迎[点赞、收藏、关注]哦~ 1、先安装CrossOver。网上有许多和谐版&#xff0c;可自行搜索。&#xff08;pd虚拟机里运行黑神话估计够呛的&#xff09; 2、运行CrossOver&#xf…...

『大模型笔记』Docker如何清理Build Cache!

Docker如何清理Build Cache! 文章目录 一. docker system df1. 镜像(Images)2. 容器(Containers)3. 本地卷(Local Volumes)4. 构建缓存(Build Cache)5. 总结二. 构建缓存(Build Cache)删除有什么影响1. 镜像构建速度变慢2. 磁盘空间被释放3. 不会影响已构建和运行的…...

如何使用 Python 读取数据量庞大的 excel 文件

使用 pandas.read_excel 读取大文件时&#xff0c;的确会遇到性能瓶颈&#xff0c;特别是对于10万行20列这种规模的 .xlsx 文件&#xff0c;常规的 pandas 方法可能会比较慢。 要提高读取速度&#xff0c;关键是找到更高效的方式处理 Excel 文件&#xff0c;特别是在 Python 的…...

c语言200例 067

大家好&#xff0c;欢迎来到无限大的频道 今天给大家带来的是c语言200例 题目要求&#xff1a; 设计一个共用体类型&#xff0c;使其成员包含多种数据类型&#xff0c;根据不同的数据类型&#xff0c;输出不同的结果 要设计一个共用体&#xff08;union&#xff09;类型&…...

RabbitMQ的高级特性-死信队列

死信(dead message) 简单理解就是因为种种原因, ⽆法被消费的信息, 就是死信. 有死信, ⾃然就有死信队列. 当消息在⼀个队列中变成死信之后&#xff0c;它能被重新被发送到另⼀个交换器 中&#xff0c;这个交换器就是DLX( Dead Letter Exchange ), 绑定DLX的队列, 就称为死信队…...

Python 复制PDF中的页面

操作PDF文档时&#xff0c;复制其中的指定页面可以帮助我们从PDF文件中提取特定信息&#xff0c;如文本、图表或数据等&#xff0c;以便在其他文档中使用。复制PDF页面也可以实现在不同文件中提取页面&#xff0c;以创建一个新的综合文档。 本文将介绍如何使用Python 在同一文档…...

Sql Developer日期显示格式设置

默认时间格式显示 设置时间格式&#xff1a;工具->首选项->数据库->NLS->日期格式: DD-MON-RR 修改为: YYYY-MM-DD HH24:MI:SS 设置完格式显示&#xff1a;...

IP地址与智能家居能够碰撞出什么样的火花呢?

感应灯、远程遥控空调&#xff0c;自动感应窗帘——智能家居已经在正逐步走入我们的生活&#xff0c;为我们带来前所未有的便捷与舒适体验。而在这一进程中&#xff0c;IP地址又能够与智能家居碰撞出什么样的火花呢&#xff1f; 一、IP地址&#xff1a;智能家居的连接基石 智…...

人工智能技术在电磁场与微波技术专业的应用

在人工智能与计算电磁学的融合背景下&#xff0c;电磁学的研究和应用正在经历一场革命。计算电磁 学是研究电磁场和电磁波在不同介质中的传播、散射和辐射等问题的学科&#xff0c;它在通信、雷达、无 线能量传输等领域具有广泛的应用。随着人工智能技术的发展&#xff0c;这一…...

The First项目报告:探索Yield Guild Games运行机制与发展潜力

在探索数字娱乐与金融融合的全新疆域中&#xff0c;GameFi&#xff08;游戏化金融&#xff09;以其独特的魅力引领了一场前所未有的变革。这一创新概念&#xff0c;最初由MixMarvel的CSO Mary Ma在2019年底乌镇大会的远见卓识中首次提出&#xff0c;它将去中心化金融&#xff0…...

(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)

题目&#xff1a;3442. 奇偶频次间的最大差值 I 思路 &#xff1a;哈希&#xff0c;时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况&#xff0c;哈希表这里用数组即可实现。 C版本&#xff1a; class Solution { public:int maxDifference(string s) {int a[26]…...

铭豹扩展坞 USB转网口 突然无法识别解决方法

当 USB 转网口扩展坞在一台笔记本上无法识别,但在其他电脑上正常工作时,问题通常出在笔记本自身或其与扩展坞的兼容性上。以下是系统化的定位思路和排查步骤,帮助你快速找到故障原因: 背景: 一个M-pard(铭豹)扩展坞的网卡突然无法识别了,扩展出来的三个USB接口正常。…...

反向工程与模型迁移:打造未来商品详情API的可持续创新体系

在电商行业蓬勃发展的当下&#xff0c;商品详情API作为连接电商平台与开发者、商家及用户的关键纽带&#xff0c;其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息&#xff08;如名称、价格、库存等&#xff09;的获取与展示&#xff0c;已难以满足市场对个性化、智能…...

3.3.1_1 检错编码(奇偶校验码)

从这节课开始&#xff0c;我们会探讨数据链路层的差错控制功能&#xff0c;差错控制功能的主要目标是要发现并且解决一个帧内部的位错误&#xff0c;我们需要使用特殊的编码技术去发现帧内部的位错误&#xff0c;当我们发现位错误之后&#xff0c;通常来说有两种解决方案。第一…...

【Go】3、Go语言进阶与依赖管理

前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课&#xff0c;做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程&#xff0c;它的核心机制是 Goroutine 协程、Channel 通道&#xff0c;并基于CSP&#xff08;Communicating Sequential Processes&#xff0…...

反射获取方法和属性

Java反射获取方法 在Java中&#xff0c;反射&#xff08;Reflection&#xff09;是一种强大的机制&#xff0c;允许程序在运行时访问和操作类的内部属性和方法。通过反射&#xff0c;可以动态地创建对象、调用方法、改变属性值&#xff0c;这在很多Java框架中如Spring和Hiberna…...

C# SqlSugar:依赖注入与仓储模式实践

C# SqlSugar&#xff1a;依赖注入与仓储模式实践 在 C# 的应用开发中&#xff0c;数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护&#xff0c;许多开发者会选择成熟的 ORM&#xff08;对象关系映射&#xff09;框架&#xff0c;SqlSugar 就是其中备受…...

《基于Apache Flink的流处理》笔记

思维导图 1-3 章 4-7章 8-11 章 参考资料 源码&#xff1a; https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...

MySQL 部分重点知识篇

一、数据库对象 1. 主键 定义 &#xff1a;主键是用于唯一标识表中每一行记录的字段或字段组合。它具有唯一性和非空性特点。 作用 &#xff1a;确保数据的完整性&#xff0c;便于数据的查询和管理。 示例 &#xff1a;在学生信息表中&#xff0c;学号可以作为主键&#xff…...

springboot 日志类切面,接口成功记录日志,失败不记录

springboot 日志类切面&#xff0c;接口成功记录日志&#xff0c;失败不记录 自定义一个注解方法 import java.lang.annotation.ElementType; import java.lang.annotation.Retention; import java.lang.annotation.RetentionPolicy; import java.lang.annotation.Target;/***…...