区间合并 | OI笔记

区间和并

基本思想：

给定多个区间，快速取出多个区间的并集

实现方式：

1. 按区间左端点排序
2. 动态维护区间，会出现三种情况：

对于第一种情况：维持原来的起始点st和结束点ed即可
对于第二种情况：将尾节点更新成 2 区间的尾节点
对于第三种情况：将维护的此区间存入答案，将 3 区间作为新的动态维护空间

例题：

Acwing803 - 区间合并

typedef pair<int, int> P;

const int N = 100000;

int n;
vector<P> segs; // 表示所有区间 

void merge (vector<P> &segs)
{
	
	vector<P> ans;
	// 用于存储合并区间后的结果 
	sort(segs.begin(), segs.end());
	// sort 对 pair进行排序时，先根据first关键字排序，再根据second关键字排序
	int st = -2e9, ed = -2e9;
	// 依据题目数据范围而定，边界值
	for (auto seg : segs) 
	{
		if (ed < seg.first)
        {
            if (st != -2e9)
            	ans.push_back({st, ed});
			st = seg.first;
			ed = seg.second;
			
        }
		else ed = max(ed, seg.second);
	}
	// 循环合并区间 
	if (st != -2e9) ans.push_back({st, ed});
	// 对segs判空 
	segs = ans;
	// 更新区间 
}

int main()
{
	cin >> n;
	for (int i = 0; i < n; i ++)
	{
		int l, r;
		cin >> l >> r;
		segs.push_back({l, r});
	}
	// 读入
	
	merge(segs);
	// 合并区间处理 
	cout << segs.size() << endl;
	return 0; 
}