区间合并(C++模板)

//区间合并(模板)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef pair<int, int>PA;
vector<PA>segs;
int n;

int Hebing(vector<PA>& segs)
{
	vector<PA>res;
	sort(segs.begin(), segs.end());
	int st = -2e9, ed = -2e9;
	for (PA seg : segs)
	{
		if (ed < seg.first)
		{
			if (ed != -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()
{
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		int l, r;
		scanf("%d %d", &l, &r);
		segs.push_back({ l,r });
	}
	Hebing(segs);
	printf("%d\n", segs.size());//合并区间后的区间个数
	return 0;
}