企业官网建设流程全解析

LeetCode-Go 题解 1235：Maximum 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].

You're 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。

示例与约束条件

示例 1

Input: 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），无法同时选择。

示例 2

Input: 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），则无法再选其他工作，总收益反而不如组合选择。

示例 3

Input: startTime = [1,1,1], endTime = [2,3,4], profit = [5,6,4] Output: 6

三份工作全部在时间 1 开始、互相重叠，只能选其中收益最高的一份，答案为 6。

数据范围（Constraints）

• 1 <= startTime.length == endTime.length == profit.length <= 5 * 10^4
• 1 <= startTime[i] < endTime[i] <= 10^9
• 1 <= profit[i] <= 10^4

数据规模达到5 * 10^4，时间范围达到10^9，这意味着：

• 不能用 O(n²) 的朴素枚举（约 25 亿次比较）；
• 不能按时间轴建数组做动态规划（时间上限太大）；
• 必须采用 O(n log n) 级别的算法：排序 + 二分查找 + 动态规划。

解题思路：排序、二分、DP 三步走

区间类题目有一个通用经验：先考虑能否排序。对于"任务 / 区间"类问题，排序往往能把"谁和谁可能重叠"的复杂关系转化为有序结构上的二分查找。

本题的核心思路是：

1. 按结束时间排序：将所有任务按endTime从小到大排序；若结束时间相同，则按收益从小到大排序（排序规则见下文源码）；
2. 定义 DP 状态：dp[i]表示排序后前i + 1份工作（下标0..i，对应原文档中"前 i 份工作"的 0 基表示）能获得的最大收益；
3. 二分查找"最后一个兼容任务"：对每个任务i，在它之前（j < i）查找满足jobs[j].endTime <= jobs[i].startTime的最大下标low，即最后一个与任务i不重叠的任务；
4. 状态转移：决定"选或不选"任务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.Interface（Len/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[mid+1].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] }

关键点逐条说明：

1. 初始化：dp[0] = jobs[0].profit，即只考虑排序后第一份工作时的最大收益就是它本身的收益。题解文档中写的是dp[0] = job[1].profit，这属于文档笔误，源码中job下标从 0 开始；
2. 二分查找：对每个任务i，在[0, i-1]范围内查找"最后一个满足endTime <= startTime[i]的下标"。mid := low + (high-low)>>1使用位运算取中值，(high-low)>>1等价于(high-low)/2，可避免溢出风险，这是 Go 二分查找的常见写法；
3. 转移分支：
   • 查找到兼容任务（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)；
4. 答案：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.mod（go 1.19）的版本要求，在题目包内自行实现。

复杂度分析

其中n = startTime.length，最大为5 * 10^4，O(n log n) 的复杂度在该数据规模下可以在毫秒级完成，完全满足题目时限要求。

测试验证：仓库自带用例

仓库为本题编写了单元测试 1235. Maximum Profit in Job Scheduling_test.go，采用question1235/para1235/ans1235的结构化用例组织方式，覆盖以下 4 组输入输出：

前 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 -covermode=atomic -coverprofile=coverage.txt ./leetcode/...的方式对全部 LeetCode 题解做覆盖率采集，说明本仓库对每个题解均要求"可测试、可验证"，本题自然也不例外。

边界情况与易错点

1. 首尾相接不算重叠：判断兼容性用的是endTime <= startTime而非<，这与题目"在 X 结束可立刻开始在 X 的工作"的规则完全对应，源码第 22、28 行均为<=判断；
2. 找不到兼容任务：当任务i与之前所有任务重叠时，转移方程退化为max(dp[i-1], jobs[i].profit)。这一分支在示例 3（三个任务全部从时间 1 开始）中会被走到；
3. dp 下标语义：dp[i]表示"排序后前 i+1 份工作"的最优收益（0 基），最终答案是dp[len(startTime)-1]而非dp[len(startTime)]；
4. 排序键选择：本题必须按endTime排序而非startTime，因为 DP 需要依赖"所有结束时间早于当前开始时间的任务"这个前缀，只有endTime有序才能二分；
5. 收益同值排序的稳定性：Less中结束时间相同时按收益升序，这一细节保证sort.Sort结果确定，配合二分查找行为可复现。

题目变形与延伸

1235是带权重区间调度问题的标准形态，掌握它之后可以顺带解决一批同类题目：

• 区间 DP 无权重版本（如"无重叠区间"类问题）可以在此基础上去掉权重、改求数量或长度；
• 本题的排序 + 二分 + DP 三板斧，同样适用于"会议室 / 教室排课""服务器任务调度""广告位排期"等真实业务中的收益最大化场景；
• 若约束改为"同一时刻只能执行一个任务且任务可分割"，则需要换用贪心或优先队列思路，与本题的 DP 框架有所区别。

在 LeetCode-Go 仓库中，0300.Longest-Increasing-Subsequence、0435.Non-overlapping-Intervals 等题目同样涉及区间排序与 DP / 贪心的组合，可作为延伸阅读，帮助建立"区间问题先排序"的解题直觉。

总结

本题的核心收获可以浓缩为三个步骤：

1. 排序：按endTime升序（同值按profit升序）排序，为二分查找建立单调结构；
2. 二分：对每个任务查找最后一个endTime <= startTime的兼容任务，O(log n) 定位最优接续点；
3. 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