归档157

600 字

3 分钟

区间合并

2025-10-05

数据结构与算法

区间合并#

区间合并用来处理多个区间之间的重叠关系。

比如：

1
[1, 3] 和 [2, 4]

这两个区间有交集，可以合并成：

1
[1, 4]

1、问题描述#

给出若干个区间，要求把所有有交集的区间合并，最后得到互不重叠的区间。

例如：

1
[1, 3] [2, 6] [8, 10] [9, 12]

合并后：

1
[1, 6] [8, 12]

2、核心思路#

区间合并一般分两步：

1
1. 按左端点从小到大排序
2
2. 从前往后维护当前正在合并的区间 [st, ed]

排序后，只需要看当前区间和维护区间是否相交。

3、如何判断是否相交#

假设当前维护区间是：

1
[st, ed]

新来的区间是：

1
[l, r]

如果：

1
ed < l

说明两个区间完全分开，需要开启一个新区间。

否则说明有交集，可以合并：

1
ed = max(ed, r)

4、C++ 模板#

1
#include <bits/stdc++.h>
2
using namespace std;
3

4
typedef pair<int, int> PII;
5

6
int n;
7
vector<PII> segs;
8

9
void merge_segments(vector<PII>& segs) {
10
    vector<PII> res;
11

12
    sort(segs.begin(), segs.end());
13

14
    int st = -2e9;
15
    int ed = -2e9;
16

17
    for (auto seg : segs) {
18
        int l = seg.first;
19
        int r = seg.second;
20

21
        if (ed < l) {
22
            if (st != -2e9) res.push_back({st, ed});
23
            st = l;
24
            ed = r;
25
        } else {
26
            ed = max(ed, r);
27
        }
28
    }
29

30
    if (st != -2e9) res.push_back({st, ed});
31

32
    segs = res;
33
}
34

35
int main() {
36
    cin >> n;
37

38
    for (int i = 0; i < n; i++) {
39
        int l, r;
40
        cin >> l >> r;
41
        segs.push_back({l, r});
42
    }
43

44
    merge_segments(segs);
45

46
    cout << segs.size() << endl;
47
    return 0;
48
}

5、手推一遍#

输入：

1
[1, 3] [2, 6] [8, 10] [9, 12]

先排序，顺序不变。

处理 [1, 3]：

1
当前区间 = [1, 3]

处理 [2, 6]，因为 2 <= 3，有交集：

1
当前区间 = [1, 6]

处理 [8, 10]，因为 6 < 8，开启新区间：

1
保存 [1, 6]
2
当前区间 = [8, 10]

处理 [9, 12]，有交集：

1
当前区间 = [8, 12]

最后保存 [8, 12]。

6、容易写错的地方#

（1）忘记先排序#

不排序的话，无法保证只和当前维护区间比较就够了。

（2）最后一个区间忘记加入答案#

循环结束后还要：

1
if (st != -2e9) res.push_back({st, ed});

（3）相邻端点是否合并要看题意#

当前模板中：

1
if (ed < l)

表示 [1, 3] 和 [3, 5] 会合并。

如果题目认为端点相接不算重叠，就要改成：

1
if (ed <= l)

总结#

区间合并的关键词是：

1
按左端点排序 + 维护当前右端点

只要能判断新区间是否和当前区间相交，代码就很直接。

文章分享

如果这篇文章对你有帮助，欢迎分享给更多人！

区间合并

https://blog.tjcheng.cn/posts/migrated/old-83/

作者

TengJinCheng

发布于