尧图网页设计 
LeetCode-Go 题解 1235Maximum Profit in Job Scheduling动态规划 二分查找解决带权重区间调度【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本文基于 LeetCode-Go 仓库中 1235.Maximum-Profit-in-Job-Scheduling 题解文档 及其 Go 源码 与 测试用例完整讲解带权重区间调度Weighted Interval Scheduling这一类高频面试题如何在不重叠的时间约束下通过排序 动态规划 二分查找三步得到最大总报酬。读完本文你将掌握该题目的状态转移方程推导、Go 语言实现细节、二分查找边界处理技巧以及如何用仓库自带测试用例验证正确性。题目回顾任务不重叠收益最大化英文原题We havenjobs, where every job is scheduled to be done fromstartTime[i]toendTime[i], obtaining a profit ofprofit[i].Youre given thestartTime,endTimeandprofitarrays, you need to output the maximum profit you can take such that there are no 2 jobs in the subset with overlapping time range.If you choose a job that ends at timeXyou will be able to start another job that starts at timeX.题目大意你打算利用空闲时间做兼职工作赚零花钱。这里有n份兼职工作每份工作预计从startTime[i]开始到endTime[i]结束报酬为profit[i]。给你一份兼职工作表包含开始时间startTime、结束时间endTime和预计报酬profit三个数组计算并返回可以获得的最大报酬。注意两条关键规则重叠即冲突时间上出现重叠的 2 份工作不能同时进行首尾相接允许如果选择的工作在时间X结束那么可以立刻进行在时间X开始的下一份工作即endTime startTime不算重叠。这是经典的加权区间调度Weighted Interval Scheduling问题也是日常排班、资源分配、任务规划类业务场景的抽象原型在 LeetCode 上难度为 Hard。示例与约束条件示例 1Input: startTime [1,2,3,3], endTime [3,4,5,6], profit [50,10,40,70] Output: 120 Explanation: The subset chosen is the first and fourth job. Time range [1-3][3-6] , we get profit of 120 50 70.选择第 1 份[1,3] 收益 50与第 4 份[3,6] 收益 70工作二者在时间 3 处首尾相接总收益 120。注意第 3 份工作单独收益 40与第 1 份重叠都从 3 开始一个到 4、一个到 5无法同时选择。示例 2Input: startTime [1,2,3,4,6], endTime [3,5,10,6,9], profit [20,20,100,70,60] Output: 150 Explanation: The subset chosen is the first, fourth and fifth job. Profit obtained 150 20 70 60.选择 [1,3]20、[4,6]70、[6,9]60三份工作首尾相接总收益 150。若贪心选择收益最高的 [3,10]100则无法再选其他工作总收益反而不如组合选择。示例 3Input: startTime [1,1,1], endTime [2,3,4], profit [5,6,4] Output: 6三份工作全部在时间 1 开始、互相重叠只能选其中收益最高的一份答案为 6。数据范围Constraints1 startTime.length endTime.length profit.length 5 * 10^41 startTime[i] endTime[i] 10^91 profit[i] 10^4数据规模达到5 * 10^4时间范围达到10^9这意味着不能用 O(n²) 的朴素枚举约 25 亿次比较不能按时间轴建数组做动态规划时间上限太大必须采用 O(n log n) 级别的算法排序 二分查找 动态规划。解题思路排序、二分、DP 三步走区间类题目有一个通用经验先考虑能否排序。对于任务 / 区间类问题排序往往能把谁和谁可能重叠的复杂关系转化为有序结构上的二分查找。本题的核心思路是按结束时间排序将所有任务按endTime从小到大排序若结束时间相同则按收益从小到大排序排序规则见下文源码定义 DP 状态dp[i]表示排序后前i 1份工作下标0..i对应原文档中前 i 份工作的 0 基表示能获得的最大收益二分查找最后一个兼容任务对每个任务i在它之前j i查找满足jobs[j].endTime jobs[i].startTime的最大下标low即最后一个与任务i不重叠的任务状态转移决定选或不选任务i取两者较大值。仓库 题解文档 中给出的状态转移方程原文描述为查找upper_bound此处结合源码修正为严格语义若找到兼容任务low则dp[i] max(dp[i-1], dp[low] jobs[i].profit)若找不到任何兼容任务包括low本身与任务i重叠则dp[i] max(dp[i-1], jobs[i].profit)最终答案保存在dp[len(startTime)-1]中即考虑完全部任务后的最大收益。需要说明原文档中这两条转移方程的文字描述存在笔误两条都写成了如果能找到本仓库 Go 实现 是语义的权威依据本文以上述两条为准。为什么二分查找可行有序结构是关键由于jobs已按endTime升序排列endTime序列单调不减因此满足endTime startTime[i]的下标集合在排序数组中构成一个前缀区间。此时可以用二分查找在 O(log n) 时间内定位最后一个满足条件的下标low所有下标0..low的任务都与任务i不重叠其中收益最优的组合就是dp[low] profit[i]完全不需要逐个遍历比较复杂度从 O(n²) 降至 O(n log n)。源码逐行解析仓库中的完整实现位于 1235. Maximum Profit in Job Scheduling.go下面按模块拆解。1. 任务结构体与排序规则type job struct { startTime int endTime int profit int } type sortJobs []job func (s sortJobs) Len() int { return len(s) } func (s sortJobs) Less(i, j int) bool { if s[i].endTime s[j].endTime { return s[i].profit s[j].profit } return s[i].endTime s[j].endTime } func (s sortJobs) Swap(i, j int) { s[i], s[j] s[j], s[i] }定义job结构体把三个平行数组startTime、endTime、profit捆绑成有序的任务列表方便排序与索引sortJobs实现标准库sort.InterfaceLen/Less/Swap三个方法排序主键是endTime升序次键是profit升序即结束时间相同按收益从小到大排序与题解文档描述一致之后通过sort.Sort(sortJobs(jobs))完成排序。排序的目的让后续二分查找建立在单调的endTime序列上。2. 主函数DP 转移与二分查找func jobScheduling(startTime []int, endTime []int, profit []int) int { jobs, dp : []job{}, make([]int, len(startTime)) for i : 0; i len(startTime); i { jobs append(jobs, job{startTime: startTime[i], endTime: endTime[i], profit: profit[i]}) } sort.Sort(sortJobs(jobs)) dp[0] jobs[0].profit for i : 1; i len(jobs); i { low, high : 0, i-1 for low high { mid : low (high-low)1 if jobs[mid1].endTime jobs[i].startTime { low mid 1 } else { high mid } } if jobs[low].endTime jobs[i].startTime { dp[i] max(dp[i-1], dp[low]jobs[i].profit) } else { dp[i] max(dp[i-1], jobs[i].profit) } } return dp[len(startTime)-1] }关键点逐条说明初始化dp[0] jobs[0].profit即只考虑排序后第一份工作时的最大收益就是它本身的收益。题解文档中写的是dp[0] job[1].profit这属于文档笔误源码中job下标从 0 开始二分查找对每个任务i在[0, i-1]范围内查找最后一个满足endTime startTime[i]的下标。mid : low (high-low)1使用位运算取中值(high-low)1等价于(high-low)/2可避免溢出风险这是 Go 二分查找的常见写法转移分支查找到兼容任务jobs[low].endTime jobs[i].startTime说明任务i可以接在0..low中收益最优的组合之后取dp[i] max(dp[i-1], dp[low]jobs[i].profit)找不到兼容任务说明任务i与之前所有任务都重叠只能单独选或沿用前 i 个任务的最优解取dp[i] max(dp[i-1], jobs[i].profit)答案dp[len(startTime)-1]即考虑完全部n个任务后的最大收益。3. max 辅助函数func max(a int, b int) int { if a b { return a } return b }一个极简的比较函数用于完成 DP 的取较大值转移。Go 1.21 之后标准库已内置max本仓库按go.modgo 1.19的版本要求在题目包内自行实现。复杂度分析维度复杂度说明时间复杂度O(n log n)排序 O(n log n)每个任务做一次二分查找 O(log n)共 n 次合计 O(n log n)空间复杂度O(n)jobs切片 O(n) dp数组 O(n)其中n startTime.length最大为5 * 10^4O(n log n) 的复杂度在该数据规模下可以在毫秒级完成完全满足题目时限要求。测试验证仓库自带用例仓库为本题编写了单元测试 1235. Maximum Profit in Job Scheduling_test.go采用question1235/para1235/ans1235的结构化用例组织方式覆盖以下 4 组输入输出startTimeendTimeprofit期望输出[1,2,3,3][3,4,5,6][50,10,40,70]120[1,2,3,4,6][3,5,10,6,9][20,20,100,70,60]150[1,1,1][2,3,4][5,6,4]6[1,2,1][3,3,3][30,40,50]50前 3 组与题解文档中的示例一致第 4 组是测试用例额外补充的边界场景——三份工作结束时间都为 3且存在完全相同的区间[1,3]用于验证结束时间相同时的排序与转移逻辑期望输出 50选择收益最高的[1,3]收益 50。测试函数通过fmt.Printf打印每组输入与jobScheduling的实际输出便于对照for _, q : range qs { _, p : q.ans1235, q.para1235 fmt.Printf(【input】:%v 【output】:%v\n, p, jobScheduling(p.startTime, p.endTime, p.profit)) }在本仓库根目录执行以下命令即可运行该测试该目录的包名为leetcode与go.mod声明的模块github.com/halfrost/LeetCode-Go对应go test -v ./leetcode/1235.Maximum-Profit-in-Job-Scheduling/仓库根目录的 gotest.sh 脚本则以go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...的方式对全部 LeetCode 题解做覆盖率采集说明本仓库对每个题解均要求可测试、可验证本题自然也不例外。边界情况与易错点首尾相接不算重叠判断兼容性用的是endTime startTime而非这与题目在 X 结束可立刻开始在 X 的工作的规则完全对应源码第 22、28 行均为判断找不到兼容任务当任务i与之前所有任务重叠时转移方程退化为max(dp[i-1], jobs[i].profit)。这一分支在示例 3三个任务全部从时间 1 开始中会被走到dp 下标语义dp[i]表示排序后前 i1 份工作的最优收益0 基最终答案是dp[len(startTime)-1]而非dp[len(startTime)]排序键选择本题必须按endTime排序而非startTime因为 DP 需要依赖所有结束时间早于当前开始时间的任务这个前缀只有endTime有序才能二分收益同值排序的稳定性Less中结束时间相同时按收益升序这一细节保证sort.Sort结果确定配合二分查找行为可复现。题目变形与延伸1235是带权重区间调度问题的标准形态掌握它之后可以顺带解决一批同类题目区间 DP 无权重版本如无重叠区间类问题可以在此基础上去掉权重、改求数量或长度本题的排序 二分 DP 三板斧同样适用于会议室 / 教室排课服务器任务调度广告位排期等真实业务中的收益最大化场景若约束改为同一时刻只能执行一个任务且任务可分割则需要换用贪心或优先队列思路与本题的 DP 框架有所区别。在 LeetCode-Go 仓库中0300.Longest-Increasing-Subsequence、0435.Non-overlapping-Intervals 等题目同样涉及区间排序与 DP / 贪心的组合可作为延伸阅读帮助建立区间问题先排序的解题直觉。总结本题的核心收获可以浓缩为三个步骤排序按endTime升序同值按profit升序排序为二分查找建立单调结构二分对每个任务查找最后一个endTime startTime的兼容任务O(log n) 定位最优接续点DP 转移选dp[low] profit[i]与不选dp[i-1]取最大答案落在dp[n-1]。整体时间复杂度 O(n log n)、空间复杂度 O(n)足以应对n 5 * 10^4、时间范围到10^9的硬约束。结合 题解文档、实现源码 与 测试用例 三者对照学习即可完整掌握这道经典 Hard 题的解法并将其推广到面试与工程中的各类区间调度场景。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode-Go 题解 1235：Maximum Profit in Job Scheduling，动态规划 + 二分查找解决带权重区间调度
LeetCode-Go 题解 1235Maximum Profit in Job Scheduling动态规划 二分查找解决带权重区间调度【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本文基于 LeetCode-Go 仓库中 1235.Maximum-Profit-in-Job-Scheduling 题解文档 及其 Go 源码 与 测试用例完整讲解带权重区间调度Weighted Interval Scheduling这一类高频面试题如何在不重叠的时间约束下通过排序 动态规划 二分查找三步得到最大总报酬。读完本文你将掌握该题目的状态转移方程推导、Go 语言实现细节、二分查找边界处理技巧以及如何用仓库自带测试用例验证正确性。题目回顾任务不重叠收益最大化英文原题We havenjobs, where every job is scheduled to be done fromstartTime[i]toendTime[i], obtaining a profit ofprofit[i].Youre given thestartTime,endTimeandprofitarrays, you need to output the maximum profit you can take such that there are no 2 jobs in the subset with overlapping time range.If you choose a job that ends at timeXyou will be able to start another job that starts at timeX.题目大意你打算利用空闲时间做兼职工作赚零花钱。这里有n份兼职工作每份工作预计从startTime[i]开始到endTime[i]结束报酬为profit[i]。给你一份兼职工作表包含开始时间startTime、结束时间endTime和预计报酬profit三个数组计算并返回可以获得的最大报酬。注意两条关键规则重叠即冲突时间上出现重叠的 2 份工作不能同时进行首尾相接允许如果选择的工作在时间X结束那么可以立刻进行在时间X开始的下一份工作即endTime startTime不算重叠。这是经典的加权区间调度Weighted Interval Scheduling问题也是日常排班、资源分配、任务规划类业务场景的抽象原型在 LeetCode 上难度为 Hard。示例与约束条件示例 1Input: startTime [1,2,3,3], endTime [3,4,5,6], profit [50,10,40,70] Output: 120 Explanation: The subset chosen is the first and fourth job. Time range [1-3][3-6] , we get profit of 120 50 70.选择第 1 份[1,3] 收益 50与第 4 份[3,6] 收益 70工作二者在时间 3 处首尾相接总收益 120。注意第 3 份工作单独收益 40与第 1 份重叠都从 3 开始一个到 4、一个到 5无法同时选择。示例 2Input: startTime [1,2,3,4,6], endTime [3,5,10,6,9], profit [20,20,100,70,60] Output: 150 Explanation: The subset chosen is the first, fourth and fifth job. Profit obtained 150 20 70 60.选择 [1,3]20、[4,6]70、[6,9]60三份工作首尾相接总收益 150。若贪心选择收益最高的 [3,10]100则无法再选其他工作总收益反而不如组合选择。示例 3Input: startTime [1,1,1], endTime [2,3,4], profit [5,6,4] Output: 6三份工作全部在时间 1 开始、互相重叠只能选其中收益最高的一份答案为 6。数据范围Constraints1 startTime.length endTime.length profit.length 5 * 10^41 startTime[i] endTime[i] 10^91 profit[i] 10^4数据规模达到5 * 10^4时间范围达到10^9这意味着不能用 O(n²) 的朴素枚举约 25 亿次比较不能按时间轴建数组做动态规划时间上限太大必须采用 O(n log n) 级别的算法排序 二分查找 动态规划。解题思路排序、二分、DP 三步走区间类题目有一个通用经验先考虑能否排序。对于任务 / 区间类问题排序往往能把谁和谁可能重叠的复杂关系转化为有序结构上的二分查找。本题的核心思路是按结束时间排序将所有任务按endTime从小到大排序若结束时间相同则按收益从小到大排序排序规则见下文源码定义 DP 状态dp[i]表示排序后前i 1份工作下标0..i对应原文档中前 i 份工作的 0 基表示能获得的最大收益二分查找最后一个兼容任务对每个任务i在它之前j i查找满足jobs[j].endTime jobs[i].startTime的最大下标low即最后一个与任务i不重叠的任务状态转移决定选或不选任务i取两者较大值。仓库 题解文档 中给出的状态转移方程原文描述为查找upper_bound此处结合源码修正为严格语义若找到兼容任务low则dp[i] max(dp[i-1], dp[low] jobs[i].profit)若找不到任何兼容任务包括low本身与任务i重叠则dp[i] max(dp[i-1], jobs[i].profit)最终答案保存在dp[len(startTime)-1]中即考虑完全部任务后的最大收益。需要说明原文档中这两条转移方程的文字描述存在笔误两条都写成了如果能找到本仓库 Go 实现 是语义的权威依据本文以上述两条为准。为什么二分查找可行有序结构是关键由于jobs已按endTime升序排列endTime序列单调不减因此满足endTime startTime[i]的下标集合在排序数组中构成一个前缀区间。此时可以用二分查找在 O(log n) 时间内定位最后一个满足条件的下标low所有下标0..low的任务都与任务i不重叠其中收益最优的组合就是dp[low] profit[i]完全不需要逐个遍历比较复杂度从 O(n²) 降至 O(n log n)。源码逐行解析仓库中的完整实现位于 1235. Maximum Profit in Job Scheduling.go下面按模块拆解。1. 任务结构体与排序规则type job struct { startTime int endTime int profit int } type sortJobs []job func (s sortJobs) Len() int { return len(s) } func (s sortJobs) Less(i, j int) bool { if s[i].endTime s[j].endTime { return s[i].profit s[j].profit } return s[i].endTime s[j].endTime } func (s sortJobs) Swap(i, j int) { s[i], s[j] s[j], s[i] }定义job结构体把三个平行数组startTime、endTime、profit捆绑成有序的任务列表方便排序与索引sortJobs实现标准库sort.InterfaceLen/Less/Swap三个方法排序主键是endTime升序次键是profit升序即结束时间相同按收益从小到大排序与题解文档描述一致之后通过sort.Sort(sortJobs(jobs))完成排序。排序的目的让后续二分查找建立在单调的endTime序列上。2. 主函数DP 转移与二分查找func jobScheduling(startTime []int, endTime []int, profit []int) int { jobs, dp : []job{}, make([]int, len(startTime)) for i : 0; i len(startTime); i { jobs append(jobs, job{startTime: startTime[i], endTime: endTime[i], profit: profit[i]}) } sort.Sort(sortJobs(jobs)) dp[0] jobs[0].profit for i : 1; i len(jobs); i { low, high : 0, i-1 for low high { mid : low (high-low)1 if jobs[mid1].endTime jobs[i].startTime { low mid 1 } else { high mid } } if jobs[low].endTime jobs[i].startTime { dp[i] max(dp[i-1], dp[low]jobs[i].profit) } else { dp[i] max(dp[i-1], jobs[i].profit) } } return dp[len(startTime)-1] }关键点逐条说明初始化dp[0] jobs[0].profit即只考虑排序后第一份工作时的最大收益就是它本身的收益。题解文档中写的是dp[0] job[1].profit这属于文档笔误源码中job下标从 0 开始二分查找对每个任务i在[0, i-1]范围内查找最后一个满足endTime startTime[i]的下标。mid : low (high-low)1使用位运算取中值(high-low)1等价于(high-low)/2可避免溢出风险这是 Go 二分查找的常见写法转移分支查找到兼容任务jobs[low].endTime jobs[i].startTime说明任务i可以接在0..low中收益最优的组合之后取dp[i] max(dp[i-1], dp[low]jobs[i].profit)找不到兼容任务说明任务i与之前所有任务都重叠只能单独选或沿用前 i 个任务的最优解取dp[i] max(dp[i-1], jobs[i].profit)答案dp[len(startTime)-1]即考虑完全部n个任务后的最大收益。3. max 辅助函数func max(a int, b int) int { if a b { return a } return b }一个极简的比较函数用于完成 DP 的取较大值转移。Go 1.21 之后标准库已内置max本仓库按go.modgo 1.19的版本要求在题目包内自行实现。复杂度分析维度复杂度说明时间复杂度O(n log n)排序 O(n log n)每个任务做一次二分查找 O(log n)共 n 次合计 O(n log n)空间复杂度O(n)jobs切片 O(n) dp数组 O(n)其中n startTime.length最大为5 * 10^4O(n log n) 的复杂度在该数据规模下可以在毫秒级完成完全满足题目时限要求。测试验证仓库自带用例仓库为本题编写了单元测试 1235. Maximum Profit in Job Scheduling_test.go采用question1235/para1235/ans1235的结构化用例组织方式覆盖以下 4 组输入输出startTimeendTimeprofit期望输出[1,2,3,3][3,4,5,6][50,10,40,70]120[1,2,3,4,6][3,5,10,6,9][20,20,100,70,60]150[1,1,1][2,3,4][5,6,4]6[1,2,1][3,3,3][30,40,50]50前 3 组与题解文档中的示例一致第 4 组是测试用例额外补充的边界场景——三份工作结束时间都为 3且存在完全相同的区间[1,3]用于验证结束时间相同时的排序与转移逻辑期望输出 50选择收益最高的[1,3]收益 50。测试函数通过fmt.Printf打印每组输入与jobScheduling的实际输出便于对照for _, q : range qs { _, p : q.ans1235, q.para1235 fmt.Printf(【input】:%v 【output】:%v\n, p, jobScheduling(p.startTime, p.endTime, p.profit)) }在本仓库根目录执行以下命令即可运行该测试该目录的包名为leetcode与go.mod声明的模块github.com/halfrost/LeetCode-Go对应go test -v ./leetcode/1235.Maximum-Profit-in-Job-Scheduling/仓库根目录的 gotest.sh 脚本则以go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...的方式对全部 LeetCode 题解做覆盖率采集说明本仓库对每个题解均要求可测试、可验证本题自然也不例外。边界情况与易错点首尾相接不算重叠判断兼容性用的是endTime startTime而非这与题目在 X 结束可立刻开始在 X 的工作的规则完全对应源码第 22、28 行均为判断找不到兼容任务当任务i与之前所有任务重叠时转移方程退化为max(dp[i-1], jobs[i].profit)。这一分支在示例 3三个任务全部从时间 1 开始中会被走到dp 下标语义dp[i]表示排序后前 i1 份工作的最优收益0 基最终答案是dp[len(startTime)-1]而非dp[len(startTime)]排序键选择本题必须按endTime排序而非startTime因为 DP 需要依赖所有结束时间早于当前开始时间的任务这个前缀只有endTime有序才能二分收益同值排序的稳定性Less中结束时间相同时按收益升序这一细节保证sort.Sort结果确定配合二分查找行为可复现。题目变形与延伸1235是带权重区间调度问题的标准形态掌握它之后可以顺带解决一批同类题目区间 DP 无权重版本如无重叠区间类问题可以在此基础上去掉权重、改求数量或长度本题的排序 二分 DP 三板斧同样适用于会议室 / 教室排课服务器任务调度广告位排期等真实业务中的收益最大化场景若约束改为同一时刻只能执行一个任务且任务可分割则需要换用贪心或优先队列思路与本题的 DP 框架有所区别。在 LeetCode-Go 仓库中0300.Longest-Increasing-Subsequence、0435.Non-overlapping-Intervals 等题目同样涉及区间排序与 DP / 贪心的组合可作为延伸阅读帮助建立区间问题先排序的解题直觉。总结本题的核心收获可以浓缩为三个步骤排序按endTime升序同值按profit升序排序为二分查找建立单调结构二分对每个任务查找最后一个endTime startTime的兼容任务O(log n) 定位最优接续点DP 转移选dp[low] profit[i]与不选dp[i-1]取最大答案落在dp[n-1]。整体时间复杂度 O(n log n)、空间复杂度 O(n)足以应对n 5 * 10^4、时间范围到10^9的硬约束。结合 题解文档、实现源码 与 测试用例 三者对照学习即可完整掌握这道经典 Hard 题的解法并将其推广到面试与工程中的各类区间调度场景。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考