基本思路

区间合并，就是把有交集的两个集合进行合并，合并成更大的区间，即取两个区间的并集。其实会判断是否有交集自己就会了。

算法步骤：

用pair存左右区间，最好养成习惯左闭右闭，即第 i 个区间： $[l_i, r_i]$
对每个区间进行排序

sort 对 pair 排序时，优先以左端点排序，再以右端点排序。默认就是
假设我们从前往后扫描到了第 i 个区间，那么第 i 个区间和当前维护的区间的关系有三种：

假设当前维护区间：$[l, r]$

第 i 个区间：$[l_i, r_i]$

因为已经排过序了，所以 $l_i < l$
1. 第 i 个区间在当前维护的区间的内部
  
  即： $l_i < r \ r_i < r$
2. 第 i 个区间和当前维护的区间有交集，但不完全在维护的区间的内部
  
  即：$l_i < r \ r_i > r$
3. 第 i 个区间和当前维护的区间没有交集
  
  即：$l_i > r$

例题

题目

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

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

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

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

输入格式
第一行包含整数 n。

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

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

数据范围
1≤n≤100000,
−109≤li≤ri≤109

输入样例：

5
1 2
2 4
5 6
7 8
7 9

输出样例：

3

代码

#include <iostream>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;
const int N = 100005;
int n, l, r, ans = 1;
PII a[N]; // a 存区间

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> a[i].first >> a[i].second;
    }
    sort(a, a+n);
    l = a[0].first;
    r = a[0].second;
    for (int i = 1; i < n; ++i) {
        if (a[i].first > r) { // 没有交集(情况3)
            ++ans;
            l = a[i].first;
            r = a[i].second;
        } else if(a[i].second > r) { // 有交集但不包含(情况2)
            r = a[i].second;
        }
    }
    cout << ans << endl;
    return 0;
}