C++如何求解带权重的区间调度问题-C++-PHP中文网

带权重的区间调度问题是选择互不重叠区间使总权重最大，属典型动态规划问题；贪心失效，需按结束时间排序后定义dp[i]为前i+1个区间的最大权重和，状态转移通过线性查找兼容前驱实现o(n²)解法。

c++如何求解带权重的区间调度问题

什么是带权重的区间调度问题

它不是简单选最多不重叠区间，而是每个区间 [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、代码审查。

下载

sort(intervals.begin(), intervals.end(), [](const auto& a, const auto& b) {
    return a.end  dp(n, 0);
dp[0] = intervals[0].weight;
for (int i = 1; i = 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; // 最大合法前驱索引</int>