带权重的区间调度问题是选择互不重叠区间使总权重最大，属典型动态规划问题；贪心失效，需按结束时间排序后定义dp[i]为前i+1个区间的最大权重和，状态转移通过线性查找兼容前驱实现O(n²)解法。
什么是带权重的区间调度问题
它不是简单选最多不重叠区间，而是每个区间 [start, end) 带一个权重 weight，目标是选出互不重叠的子集，使总权重最大。这是典型的动态规划问题，贪心策略（如按结束时间排序后贪心）在这里失效——因为高权重的长区间可能“挡住”多个低权重短区间，反而更优。
如何用 DP 实现 O(n²) 解法
核心思路：对所有区间按 end 升序排序，定义 dp[i] 表示考虑前 i+1 个区间时的最大权重和。状态转移依赖于“最后一个选中的区间”能否与当前区间兼容。
关键操作是：对每个 i，找最大的 j ，使得 <code>intervals[j].end 。可用线性扫描或二分查找加速。
示例代码片段（C++17）：
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
立即学习“C++免费学习笔记（深入）”；
sort(intervals.begin(), intervals.end(), [](const auto& a, const auto& b) {
return a.end < b.end;
});
vector<int> dp(n, 0);
dp[0] = intervals[0].weight;
for (int i = 1; i < n; ++i) {
int include = intervals[i].weight;
int j = i - 1;
while (j >= 0 && intervals[j].end > intervals[i].start) --j;
if (j >= 0) include += dp[j];
dp[i] = max(dp[i-1], include);
}- 注意
intervals是自定义结构体，含start、end、weight - 这里用的是线性找前驱，复杂度 O(n²)；若改用
lower_bound配合预存end数组，可压到 O(n log n) - 别忘了初始化
dp[0]，否则dp[i-1]在i=0会越界
为什么不能直接用 std::lower_bound 在原 vector 上二分
因为 std::lower_bound 要求容器按查找键有序，而你查的是 intervals[j].end ，即需在 <code>end 值序列上查第一个 ≥ intervals[i].start 的位置。但原 intervals 是按 end 排的，所以可以提取 ends 数组：
vector<int> ends; for (const auto& x : intervals) ends.push_back(x.end); // 然后对每个 i： int pos = lower_bound(ends.begin(), ends.end(), intervals[i].start) - ends.begin(); int j = pos - 1; // 最大合法前驱索引
- 必须用
pos - 1，不是pos：因为我们要end ，而非 <code>end >= start - 若
pos == 0，说明没有合法前驱，此时j = -1，对应 “不加任何前置区间” - 别把
ends和intervals索引搞混——它们严格对齐，所以j可直接用于dp[j]
重构为结构化函数时容易漏掉的边界
写成独立函数（如 int weightedIntervalScheduling(const vector<Interval>& intervals)）时，最常出错的是空输入和单元素输入处理：
- 输入为空 → 返回 0，不是崩溃或未定义行为
- 输入只有一个区间 → 直接返回其
weight，不能跳进循环导致越界 - 区间本身无效（
start > end）要提前过滤，否则排序后逻辑错乱 - 权重为负？题目通常假设非负，但若允许负值，DP 初始化和转移需额外判断——默认解法不处理负权
实际工程中，建议用 vector<tuple<int,int,int>> 或结构体 + explicit 构造，避免字段顺序误用。权重类型也建议显式用 long long，防止累加溢出。
