区间合并（算法）

题目

给定 $n$ 个区间 $l_i, r_i]$ ，要求合并所有有交集的区间。

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

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

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

输入格式：
第一行包含整数 $n$ 。
接下来 $n$ 行，每行包含两个整数 $l$ 和 $r$ 。

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

数据范围：
$1 \leq n \leq 100000$
$10^9≤l_i≤r_i≤10^9$

输入样例：

输出样例：

代码实现

#define _CRT_SECURE_NO_WARNINGS

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

using namespace std;
typedef pair<int, int> PII;
vector<PII> segs;

void merge()
{
	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;
}
int main()
{
	int n;
	cin >> n;
	while (n--)
	{
		int l, r;
		cin >> l >> r;
		segs.push_back({ l, r });
	}
	merge();
	cout << segs.size() << endl;
	return 0;
}