区间合并模板

// 将所有存在交集的区间合并
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;
}

例题

#include <iostream>
#include <vector>

using namespace std;

typedef pair<int, int> PII;
const int N = 100010;

int n;
vector<PII> segs;

void merge(vector<PII> &segs)
{
	vector<PII> res;
	
	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()
{
	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;
}

测试样例

输入样例
5
1 2
2 4
5 6
7 8
7 9

输出样例
3