区间合并实现代码详解

引言

区间合并是数据结构与算法领域中的一个常见问题，在处理一些涉及时间或空间维度的数据时尤为重要。例如，对于一组时间区间的合并、地理范围的覆盖分析等场景都有应用价值。本文将详细介绍如何通过C++来实现区间合并，并提供具体的代码示例。

区间定义

在讨论区间合并之前，我们需要先明确何为一个“区间”。假设我们有若干个闭合区间 [start, end]，其中 start 和 end 分别代表区间的起点和终点。我们的目标是将所有相交或相邻的区间合并成尽可能少的几个连续的区间。

问题定义

给定多个区间 [[s1, e1], [s2, e2], ..., [sn, en]]，需要进行以下操作：

合并所有的相交或相邻区间。
返回合并后的区间列表。

示例

假设输入的区间为：[[1, 3], [2, 6], [8, 10], [15, 18]]

期望输出为 [[1, 6], [8, 10], [15, 18]]

实现思路

步骤一：排序

首先，我们需要将所有区间的起点进行排序。这样做的目的是确保相同起点的区间被相邻放置在一起，从而能够更容易地判断它们是否需要合并。

步骤二：遍历并合并

使用一个临时变量来存储当前处理区间的终点值，并通过遍历的方式检查接下来的每个区间是否与当前区间相交或邻接。如果是，则更新当前区间的终点；如果不是，则将当前区间添加到结果列表中，同时初始化一个新的区间。

步骤三：返回最终结果

完成所有区间的合并后，返回最后得到的结果列表。

代码实现

下面是使用C++实现上述思路的具体代码：

#include <iostream>
#include <vector>

using namespace std;

struct Interval {
    int start;
    int end;
};

class IntervalMerger {
public:
    vector<Interval> merge(vector<Interval>& intervals) {
        if (intervals.empty()) return {};

        // 按照区间的起点对区间进行排序
        sort(intervals.begin(), intervals.end(),
             [](const Interval& a, const Interval& b) { return a.start < b.start; });

        vector<Interval> merged;
        for (const auto& interval : intervals) {
            if (!merged.empty() && merged.back().end >= interval.start) {
                // 当前区间与上一个合并区间有重叠或相邻
                merged.back().end = max(merged.back().end, interval.end);
            } else {
                // 无交集，将当前区间接入结果
                merged.push_back(interval);
            }
        }

        return merged;
    }
};

int main() {
    vector<Interval> intervals = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
    IntervalMerger merger;
    auto result = merger.merge(intervals);

    for (const auto& interval : result) {
        cout << "[" << interval.start << ", " << interval.end << "] ";
    }
    return 0;
}

总结

通过上述代码，我们实现了一个基于合并相邻或相交区间的算法。这种方法的时间复杂度主要取决于排序操作（O(n log n)），其中n为区间数量；而遍历合并则为线性时间 O(n)。这使得该方法在处理大规模数据集时仍能保持较高的效率。

通过本文的介绍，我们不仅学习了如何实现区间合并，还了解到了其实际应用场景及代码的具体编写过程。希望这些内容对你有所帮助！