按结束时间升序排序才能得到最优解，因为早结束的区间为后续留出更多选择空间，数学上可证该贪心策略不劣于任意最优解；按开始时间排序或不排序会导致局部最优却全局次优。
为什么按结束时间排序才能得到最优解
区间调度问题里，贪心策略的核心不是“选最长的”或“选最早的”，而是按结束时间升序排序后每次选当前可选中结束最早的区间。这是因为早结束给后续留出更多空间，数学上能证明该策略不会比任意最优解差——任何其他选择都可以被替换成这个更早结束的而不减少总数。
常见错误是按开始时间排序，结果可能卡死在某个长区间上，后面一堆短区间全被排除；或者不排序直接遍历，完全失去贪心前提。
- 必须用
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 开始遍历。
立即学习“C++免费学习笔记（深入）”；
- 声明时写
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, int>> intervals;
for (int i = 0; i < n; ++i) {
int s, e; cin >> s >> e;
intervals.emplace_back(s, e);
}
if (intervals.empty()) { cout << 0 << endl; return 0; }
sort(intervals.begin(), intervals.end(), [](const auto& a, const auto& b) {
return a.second < b.second;
});
int count = 1;
int last_end = intervals[0].second;
for (int i = 1; i < intervals.size(); ++i) {
if (intervals[i].first >= last_end) { // 允许端点相接用 >=，严格不交用 >
++count;
last_end = intervals[i].second;
}
}
cout << count << endl;
}
注意 intervals[i].first >= last_end 这行：很多题要求“不重叠”，但数学定义中 [1,3] 和 [3,5] 是 disjoint 的，是否接受取决于题目描述——漏看这点会导致样例通过但评测 WA。
扩展到带权重的加权区间调度怎么办
原题是“最多选几个”，属于无权版本；一旦每个区间带权重（如价值、优先级），贪心失效，必须转为动态规划。此时 sort 仍按结束时间，但状态转移变成：对每个区间 i，找最后一个满足 end[j] < start[i] 的 j，然后 dp[i] = max(dp[i-1], dp[j] + weight[i])。
这里最容易忽略的是查找 j 的效率——暴力扫是 O(n²)，用 upper_bound 配合预存的结束时间数组可压到 O(n log n)。但前提是结束时间数组已排序（恰好就是我们排好的），所以别在 DP 里再排一遍。
- 别试图用贪心“加个权重修正”来应付加权版——不存在通用修正公式
-
std::upper_bound查的是第一个 > target 的位置，要找 ≤ target 的最后一个，得用std::prev(upper_bound(...)) - DP 数组长度必须是
n+1，留出dp[0] = 0边界，否则j = -1时难处理
