按结束时间升序排序才能得到最优解，因为早结束的区间为后续留出更多选择空间，数学上可证该贪心策略不劣于任意最优解；按开始时间排序或不排序会导致局部最优却全局次优。
为什么按结束时间排序才能得到最优解
区间调度问题里，贪心策略的核心不是“选最长的”或“选最早的”，而是按结束时间升序排序后每次选当前可选中结束最早的区间。这是因为早结束给后续留出更多空间，数学上能证明该策略不会比任意最优解差——任何其他选择都可以被替换成这个更早结束的而不减少总数。
常见错误是按开始时间排序，结果可能卡死在某个长区间上，后面一堆短区间全被排除；或者不排序直接遍历，完全失去贪心前提。
- 必须用
std::sort配合自定义比较函数，不能只靠std::vector::sort默认行为 - 比较函数要写成
[&](const auto& a, const auto& b) { return a[1] ，索引 <code>1是结束时间（假设每个区间是{start, end}） - 如果输入含闭区间且端点重叠（如
[1,3]和[3,5]），需明确是否允许相接：允许就用last_end ，否则用 <code>last_end
如何用 vector> 存储并避免越界访问
用 std::vector<:pair int>></:pair> 存区间最直观，first 是开始，second 是结束。但注意：C++ 中 pair 的成员名固定，别写成 .start 或 .end——那会编译失败。
实际编码时容易在循环中多取一个元素，比如用 i 却在循环体里访问 <code>intervals[i+1]，导致越界。安全做法是初始化 count = 1、last_end = intervals[0].second，然后从 i = 1 开始遍历。
- 声明时写
vector<pair int>> intervals;</pair>，读入后立刻检查if (intervals.empty()) return 0; - 排序前确认每个
pair满足a.first ，否则 <code>sort后逻辑错乱 - 不要用
auto& p : intervals范围 for 做贪心选择——你得跳过不满足条件的，无法用简单遍历替代索引控制
完整可运行代码的关键三步
一个能直接编译运行的最小实现，核心就三步：输入解析 → 排序 → 贪心扫描。没有类封装、不引入额外结构，适合调试和验证逻辑。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n; cin >> n;
vector<pair int>> intervals;
for (int i = 0; i > s >> e;
intervals.emplace_back(s, e);
}
if (intervals.empty()) { cout = last_end) { // 允许端点相接用 >=，严格不交用 >
++count;
last_end = intervals[i].second;
}
}
cout
<p>注意 <code>intervals[i].first >= last_end</code> 这行：很多题要求“不重叠”，但数学定义中 <code>[1,3]</code> 和 <code>[3,5]</code> 是 disjoint 的，是否接受取决于题目描述——漏看这点会导致样例通过但评测 WA。</p>
<h3>扩展到带权重的加权区间调度怎么办</h3>
<p>原题是“最多选几个”，属于无权版本；一旦每个区间带权重（如价值、优先级），贪心失效，必须转为动态规划。此时 <code>sort</code> 仍按结束时间，但状态转移变成：对每个区间 <code>i</code>，找最后一个满足 <code>end[j] 的 <code>j</code>，然后 <code>dp[i] = max(dp[i-1], dp[j] + weight[i])</code>。</code></p>
<p>这里最容易忽略的是查找 <code>j</code> 的效率——暴力扫是 O(n²)，用 <code>upper_bound</code> 配合预存的结束时间数组可压到 O(n log n)。但前提是结束时间数组已排序（恰好就是我们排好的），所以别在 DP 里再排一遍。</p>
<ul>
<li>别试图用贪心“加个权重修正”来应付加权版——不存在通用修正公式</li>
<li>
<code>std::upper_bound</code> 查的是第一个 > target 的位置，要找 ≤ target 的最后一个，得用 <code>std::prev(upper_bound(...))</code>
</li>
<li>DP 数组长度必须是 <code>n+1</code>，留出 <code>dp[0] = 0</code> 边界，否则 <code>j = -1</code> 时难处理</li>
</ul>
贪心成立的前提非常具体：目标函数是计数型、约束是区间不交、收益无差异。换掉其中任一条件，就得重新评估策略。实际写题时，先盯死题目问的是“最多几个”还是“最大总权重”，这决定你是写 5 行还是 20 行。</pair></algorithm></vector></iostream>C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
