当前位置：首页 > news >正文

[贪心策略] 从“区间选点”到“最大不相交区间”：一个等价转换的深度解析

news 2026/7/16 9:18:39

1. 从生活场景理解区间问题的本质

想象你是一名忙碌的行政助理，今天需要安排多个会议。每个会议都有固定的开始和结束时间，比如会议A是9:00-10:30，会议B是10:00-11:30。这时候你就会面临一个典型的选择：如何安排才能让尽可能多的会议顺利进行而不出现时间冲突？

这就是最大不相交区间数量问题的现实映射。而有趣的是，这个问题和另一个看似不同的问题——区间选点问题（即在数轴上用最少的点覆盖所有区间）——在算法层面上是完全等价的。我第一次意识到这个等价关系时，就像发现了两把能打开同一把锁的不同钥匙。

举个具体例子：假设有三个区间[1,3], [2,4], [3,5]。要找到最大不相交区间集合，我们可以选择[1,3]和[3,5]；而要找到最少的覆盖点，我们只需要选择点3和点5（或者3和4）。你会发现最大不相交区间数量（2个）正好等于最少需要的点数（2个）。

2. 贪心策略的双重应用

解决这两个问题的核心都是按右端点排序的贪心策略。这个策略之所以有效，是因为它保证了每次选择都能为后续决策留下最大的灵活性空间。

2.1 算法步骤详解

排序阶段：将所有区间按照右端点从小到大排序。如果是C++可以用sort配合自定义比较函数，Python可以用sorted配合lambda表达式。

# Python排序示例 intervals = [(1,3), (2,4), (3,5)] intervals.sort(key=lambda x: x[1]) # 按元组第二个元素(右端点)排序

遍历选择阶段：
- 初始化已选区间的右端点end为负无穷
- 遍历每个区间：
  - 如果当前区间的左端点 > end，说明不重叠
  - 选择这个区间（或选择它的右端点作为覆盖点）
  - 更新end为当前区间的右端点

2.2 为什么这个策略能同时解决两个问题？

关键在于区间的相交关系。当几个区间有公共交点时：

它们不能同时出现在最大不相交集合中（因为相交）
但可以被同一个点覆盖（因为相交意味着存在公共点）

这就建立了两个问题的等价性：最大不相交区间数量 = 最少需要的覆盖点数。我在实际编码比赛中多次验证过这个结论，甚至可以用同一段代码AC这两个不同的问题。

3. 严格证明与算法正确性

要真正理解这个算法，我们需要从数学上证明它的正确性。这通常包含两个部分：

3.1 贪心选择性质

假设我们已经按右端点排序，记为I₁, I₂,...,Iₙ。设第一个区间是I₁=[l₁,r₁]。我们需要证明存在一个最优解包含I₁。

反证法：假设某个最优解不包含I₁，那么这个解中第一个被选的区间Iⱼ必然满足j>1且与I₁相交（因为I₁结束最早）。此时我们可以用I₁替换Iⱼ，仍然得到一个合法解，且数量不变。因此包含I₁的解也是最优解。

3.2 最优子结构性质

在选择I₁后，剩下的问题是在所有与I₁不相交的区间中寻找最大子集。这构成了一个子问题，其最优解加上I₁就是原问题的最优解。

用数学归纳法可以完整证明：对于k个区间的问题，算法能正确找到最大不相交集合。这个证明模式也解释了为什么很多贪心算法都采用类似的"选择最早结束"策略。

4. 代码实现与优化技巧

虽然算法思路简单，但实际实现时有很多值得注意的细节。下面给出C++和Python的典型实现：

4.1 C++实现（ACM风格）

#include <iostream> #include <algorithm> using namespace std; const int N = 1e5+10; struct Range { int l, r; bool operator< (const Range &W) const { return r < W.r; } } range[N]; int main() { int n; cin >> n; for (int i = 0; i < n; ++i) { int a, b; cin >> a >> b; range[i] = {a, b}; } sort(range, range + n); int res = 0, ed = -2e9; for (int i = 0; i < n; ++i) { if (ed < range[i].l) { res++; ed = range[i].r; } } cout << res << endl; return 0; }

4.2 Python实现（更简洁）

def max_non_overlapping(intervals): intervals.sort(key=lambda x: x[1]) count = 0 end = -float('inf') for interval in intervals: if interval[0] > end: count += 1 end = interval[1] return count