区间合并

步骤

  1. 根据每个区间的左端点排序
  2. 一个一个区间（对应下面的l和r）进行合并（对一个区间进行维护，对应下面的st和ed）

当前区间与维护区间的关系

因为我们按照排过的顺序进行依次处理的时候可以确保当前区间的左端点一定在当前维护区间的左端点右边（包括左端点），所以不需要考虑左边的边界问题。

  1. 包含
    无需更新维护区间
  2. 有交集
    更新维护区间的后断点ed至当前区间后端点r
  3. 无交集
    保存维护区间，更新维护区间至当前区间

板子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 将所有存在交集的区间合并
void merge(vector<PII> &segs)
{
    vector<PII> res;

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

    int st = -2e9, ed = -2e9;
    for (auto seg : segs)
        if (ed < seg.first)
        {
            if (st != -2e9) res.push_back({st, ed});
            st = seg.first, ed = seg.second;
        }
        else ed = max(ed, seg.second);

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

    segs = res;
}

例题

https://www.acwing.com/problem/content/805/

题目描述

给定 n 个区间 [l r]，要求合并所有有交集的区间。

注意如果在端点处相交，也算有交集。

输出合并完成后的区间个数。

例如：[1,3] 和 [2,6] 可以合并为一个区间 [1,6]。

输入格式

第一行包含整数 n。

接下来 n 行，每行包含两个整数 l 和 r。

输出格式

共一行，包含一个整数，表示合并区间完成后的区间个数。

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL, LL> PII;

LL n;
vector<PII> segs;

void merge(vector<PII> &segs) {
	vector<PII> res;
	
	sort(segs.begin(), segs.end());
	
	LL st = -2e9, ed = -2e9; // 当前维护的区间
	for (auto seg : segs) {
		LL l = seg.first, r = seg.second;
		if (ed < l) { //无交集
			if (st != -2e9) res.push_back({st, ed}); // 首个-2e9的区间注意不要存入了
			st = l, ed = r;
		}
		else // 包含或有交集
			ed = max(ed, r);
	}
	
	if (st != -2e9) res.push_back({st, ed}); // 保存最后一个区间，同时考虑一个区间都没有的情况
	
	segs = res;
}

int main() {
	cin >> n;
	for (LL i = 0; i < n; i++) {
		LL l, r;
		cin >> l >> r;
		segs.push_back({l, r});
	}
	
	merge(segs);
	
	cout << segs.size();
	
	return 0;
}