区间合并算法ACM实战从基础排序到贪心策略详解解决线段重叠与覆盖难题

嘿，朋友！如果你正在为 ACM 竞赛或者日常算法刷题头疼，特别是看到那种“一堆线段叠在一起，求并集长度”或者“最少需要几个点覆盖所有线段”的题目时，先深呼吸。别被那些复杂的几何直觉吓到了。

其实，这类问题有一个非常优雅且通用的解法——区间合并（Interval Merging）。它看起来简单，但里面藏着很多关于排序、贪心以及边界处理的精髓。今天，我不给你念教科书，咱们就像在实验室里调试代码一样，一步步拆解这个算法，直到你能把它写得像呼吸一样自然。

为什么我们需要“区间合并”？

想象一下，你有一堆彩色的胶带贴在了数轴上。有些胶带重叠了，有些紧挨着，有些则孤零零地分开。现在，面试官（或者题目）问你：“请把重叠或相邻的胶带粘成一条长的，最后告诉我一共有几条长胶带？”

这就是区间合并的本质：将一组有重叠或接触的区间，压缩成一组互不相交的区间。

在 ACM 中，这通常用于解决以下几类问题：

最大覆盖长度：计算所有区间的并集总长度。
最小点数覆盖：用最少的点覆盖所有区间。
事件处理：比如会议室安排、服务器资源分配等。

核心思想只有一个：排序 + 贪心。只要排序做对了，后面的逻辑就是水到渠成。

第一步：数据结构与排序的艺术

在动手合并之前，我们必须先把这些区间“排好队”。怎么排？这是很多初学者容易出错的地方。

定义区间

首先，我们需要一个结构体或类来表示区间。在 C++ 中，我们通常这样定义：

struct Interval {
    int start;
    int end;
    
    // 构造函数方便初始化
    Interval(int s, int e) : start(s), end(e) {}
};

排序规则：按起点升序

这是最关键的一步。我们必须按照区间的左端点（start）从小到大进行排序。

为什么要按左端点？ 因为合并的逻辑是“从前向后”推进的。如果我们先看了左边的起点，就能确定当前区间的起始位置。如果按右端点排序，你会发现很难判断两个区间是否重叠，因为左端点可能在任意位置跳跃。
次级排序规则： 如果左端点相同，按右端点升序还是降序都可以，但在某些特定场景下（如求最大重叠数），可能需要特殊处理。对于基础的区间合并，左端点相同的情况下，顺序影响不大，通常保持稳定性即可。

让我们看看排序的代码实现：

bool compareIntervals(const Interval& a, const Interval& b) {
    if (a.start != b.start) {
        return a.start < b.start; // 主要关键字：左端点升序
    }
    return a.end < b.end; // 次要关键字：右端点升序
}

// 使用示例
std::vector<Interval> intervals = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
std::sort(intervals.begin(), intervals.end(), compareIntervals);

排序后的结果应该是：[1, 3], [2, 6], [8, 10], [15, 18]。你看，左端点已经乖乖听话了。

第二步：贪心策略——合并的核心逻辑

现在区间排好序了，我们可以开始遍历了。这里用到的是贪心策略：我们总是尝试将当前区间与“上一个保留下来的区间”进行比较。

逻辑推演

假设我们已经维护了一个结果列表 merged。

取出第一个区间 [1, 3]，放入 merged。此时 merged = [[1, 3]]。
看下一个区间 [2, 6]。
- 它的左端点是 2。
- 前一个区间的右端点是 3。
- 因为 2 <= 3，说明它们重叠了！
- 贪心选择：既然重叠，我们就把它们合并。合并后的新区间左端点不变（因为是排序过的，前一个更小），右端点取两者最大值。
- 新右端点 = max(3, 6) = 6。
- 更新 merged 的最后一个元素为 [1, 6]。
看下一个区间 [8, 10]。
- 左端点 8。
- 前一个右端点 6。
- 因为 8 > 6，没有重叠，也不相邻（取决于题目定义，通常严格大于才是不重叠）。
- 直接将 [8, 10] 加入 merged。
继续这个过程…

关键判断条件

在代码中，我们只需要比较当前区间的左端点和结果列表中最后一个区间的右端点。

如果 current.start <= last.end：重叠，合并。更新 last.end = max(last.end, current.end)。
如果 current.start > last.end：不重叠，将 current 作为一个新的独立区间加入结果列表。

第三步：完整代码实战（C++）

光说不练假把式。下面是一个完整的、可运行的 C++ 解决方案。注意注释中的细节，那是 AC（Accepted）的关键。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Interval {
    int start;
    int end;
    Interval(int s, int e) : start(s), end(e) {}
};

class Solution {
public:
    vector<Interval> merge(vector<Interval>& intervals) {
        // 边界情况：如果没有区间，直接返回空
        if (intervals.empty()) {
            return {};
        }

        // 1. 排序：按左端点升序
        sort(intervals.begin(), intervals.end(), [](const Interval& a, const Interval& b) {
            return a.start < b.start;
        });

        vector<Interval> merged;
        
        // 2. 遍历并合并
        for (const auto& interval : intervals) {
            // 如果结果列表为空，或者当前区间与上一个区间没有重叠
            // 注意：这里判断的是 interval.start > merged.back().end
            if (merged.empty() || interval.start > merged.back().end) {
                merged.push_back(interval);
            } else {
                // 否则，存在重叠，合并区间
                // 左端点不需要变（因为已排序），右端点取较大值
                merged.back().end = max(merged.back().end, interval.end);
            }
        }

        return merged;
    }
};

// 测试用例
int main() {
    vector<Interval> input = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
    Solution sol;
    vector<Interval> result = sol.merge(input);

    cout << "Merged Intervals:" << endl;
    for (const auto& interval : result) {
        cout << "[" << interval.start << ", " << interval.end << "] ";
    }
    cout << endl;
    // 预期输出: [1, 6] [8, 10] [15, 18]

    return 0;
}

代码细节解析（给小朋友看的版本）

想象你在整理书包里的书本：

排序：你把所有书按高度从矮到高排成一排。（对应 sort）
检查重叠：你拿起第二本书，看看它是不是压在了第一本书上面。（对应 interval.start <= merged.back().end）
合并：如果是，你就把这两本书看作一本厚的书，高度取最高的那本。（对应 max(...)）
新建：如果不是，你就把它放在旁边，作为新的一摞书的开始。（对应 push_back）

这样，你最后手里剩下的每一摞书，都是互不干扰的。

进阶挑战：变体问题

区间合并不仅仅是把区间合起来，它还是解决其他复杂问题的基石。让我们看看它在 ACM 中常见的几种变体。

变体 1：计算区间并集的总长度

问题描述：给定一组区间，求它们覆盖的总长度。例如 [1, 3], [2, 6] 合并后是 [1, 6]，长度是 \(6-1=5\)。

思路：

先进行标准的区间合并。
遍历合并后的结果，累加每个区间的长度 end - start。

代码片段：

int totalLength(vector<Interval>& intervals) {
    if (intervals.empty()) return 0;
    
    sort(intervals.begin(), intervals.end(), [](const Interval& a, const Interval& b) {
        return a.start < b.start;
    });

    int length = 0;
    int prevEnd = intervals[0].end;
    int prevStart = intervals[0].start;

    for (size_t i = 1; i < intervals.size(); ++i) {
        if (intervals[i].start > prevEnd) {
            // 不重叠，累加前一个区间长度
            length += (prevEnd - prevStart);
            // 更新当前区间
            prevStart = intervals[i].start;
            prevEnd = intervals[i].end;
        } else {
            // 重叠，扩展右边界
            prevEnd = max(prevEnd, intervals[i].end);
        }
    }
    // 加上最后一个区间
    length += (prevEnd - prevStart);
    return length;
}

变体 2：最小点数覆盖所有区间

问题描述：给定一组区间，问至少需要选多少个点，使得每个区间内至少包含一个点？

思路：这是一个经典的贪心问题，但方向反过来了。

按区间的右端点升序排序。（注意：这里不是左端点！）
初始化一个点集为空，记录最后一个选择的点的位置 last_pos = -infinity。
遍历排序后的区间：
- 如果当前区间的左端点 start > last_pos，说明当前的点无法覆盖这个区间。
- 我们必须在这个区间内选一个新点。贪心策略：为了让这个点尽可能覆盖后面的区间，我们应该选当前区间的右端点作为新点。
- 更新 last_pos = current.end，计数器加一。

为什么选右端点？ 因为区间是按右端点排序的，选右端点意味着这个点能延伸到最右边，从而有最大概率覆盖后续开始的区间。

代码片段：

int minPointsToCover(vector<Interval>& intervals) {
    if (intervals.empty()) return 0;
    
    // 按右端点排序
    sort(intervals.begin(), intervals.end(), [](const Interval& a, const Interval& b) {
        return a.end < b.end;
    });

    int count = 0;
    int last_pos = INT_MIN; // 用一个极小的数表示

    for (const auto& interval : intervals) {
        // 如果当前区间的起点在最后一个点的右侧，说明没被覆盖
        if (interval.start > last_pos) {
            count++;
            last_pos = interval.end; // 贪心选择：选当前区间的右端点
        }
    }
    return count;
}

变体 3：插入新区间

问题描述：在一个已经合并好的区间列表中，插入一个新的区间，并保持列表有序且无重叠。

思路：

将新区间加入原列表。
重新对整个列表进行排序和合并。
复杂度分析：排序 \(O(N \log N)\)，合并 \(O(N)\)。总复杂度 \(O(N \log N)\)。
优化版：由于原列表已排序，可以利用二分查找找到插入位置，然后只合并受影响的局部区间，可以将复杂度降低到接近 \(O(N)\)，但在 ACM 中，通常直接调用上面的 merge 函数更稳妥，除非 \(N\) 极大且对性能有极致要求。

常见陷阱与调试技巧

在实际比赛中，即使逻辑对了，也可能因为一些细节 WA（Wrong Answer）。以下是我踩过的坑，分享给你：

闭区间 vs 开区间：
- 题目通常默认是闭区间 [start, end]。
- 如果题目说“长度为”，注意 end - start 还是 end - start + 1。例如 [1, 1] 的长度是 1 还是 0？在实数轴上是 0，在整数离散点上通常是 1。一定要看清题目定义！ 大多数 ACM 几何题是在连续数轴上，所以 [1, 3] 和 [3, 5] 在点 3 处接触，通常算作重叠或可合并（取决于具体题意，一般 start <= last_end 即合并）。
负数区间：
- 区间可以是负数的，如 [-5, -2]。排序逻辑依然适用，但初始化的 last_pos 不能用 0，要用 INT_MIN 或第一个区间的值。
嵌套区间：
- 例如 [1, 10] 和 [2, 5]。排序后，[1, 10] 在前。合并时，2 <= 10，更新右端点为 max(10, 5) = 10。结果仍是 [1, 10]。逻辑正确。
空输入：
- 永远不要忘记检查 intervals.empty()。
数据类型溢出：
- 如果坐标范围很大（如 \(10^9\)），不要用 int 存储累加长度，要用 long long。但在区间合并本身，int 通常够用，除非题目特别说明。

总结：从入门到精通的心法

区间合并算法看似简单，但它体现了算法设计中两个最重要的思想：

预处理的重要性：通过排序，我们将一个无序的、复杂的问题转化为了一个有序的、线性的问题。
贪心的正确性：在每一步做出局部最优选择（合并或延伸），最终导致全局最优解。

当你下次再遇到线段重叠、时间冲突、资源调度等问题时，先问问自己：“我能把它们看作区间吗？我能排序吗？”

如果能，那么恭喜你，你已经解出了这道题的一半。剩下的一半，就是写出那几行简洁的代码。

希望这篇文章能帮你彻底搞定区间合并。如果有具体的题目卡住了，欢迎随时拿过来，我们一起拆解！记住，编程不仅是写代码，更是理清逻辑的过程。加油！

正文

区间合并算法ACM实战从基础排序到贪心策略详解解决线段重叠与覆盖难题

为什么我们需要“区间合并”？

第一步：数据结构与排序的艺术

定义区间

排序规则：按起点升序

第二步：贪心策略——合并的核心逻辑

逻辑推演

关键判断条件

第三步：完整代码实战（C++）

代码细节解析（给小朋友看的版本）

进阶挑战：变体问题

变体 1：计算区间并集的总长度

变体 2：最小点数覆盖所有区间

变体 3：插入新区间

常见陷阱与调试技巧

总结：从入门到精通的心法

相关阅读

蔚来汽车笔试，ACM算法挑战，揭秘求职者的编程实力大考验

北理工ACM校赛：揭秘校园编程精英对决，挑战极限，探索算法奥秘！

北理工ACM战队：揭秘校园编程精英的崛起之路

“北大暑期课程官网：ACM编程挑战赛独家解析与实战技巧揭秘”

北大暑假ACM班：揭秘顶尖编程天才的摇篮，如何培养未来科技领袖？

河北学子ACM竞赛大揭秘：编程高手如何炼成？实战技巧全解析

飞机黑匣子揭秘：波音ACM如何守护飞行安全

河北ACM竞赛：揭秘大学生编程高手对决，带你领略算法魅力与挑战！

波音ACM经理揭秘：如何打造高效团队，提升企业竞争力

江西中医药大学ACM竞赛：揭秘大学生编程高手们的挑战之路