算法练习专栏算法小扩展02——如何将多个区间进行合并操作（必看）

难度：简单++

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

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

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

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

输入格式

第一行包含整数 n。

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

输出格式

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

数据范围

$$
1\le n \le 100000 \
−10^{9}≤l_{i}≤r_{i}≤10^{9}
$$

输入样例：

1
2
3
4
5
6
5
1 2
2 4
5 6
7 8
7 9

输出样例：

1
3

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
const int N = 1e5 + 10;
const int INF = 2e9;
typedef long long LL;
typedef pair<int, int> PII;
int n;
LL res;
vector<PII> query;

void merge() {
    int l,r;
    l = r = -INF;
    for(auto items:query) 
    {
        if (r < items.first) {
            res ++;
            l = items.first;
            r = items.second;
        } else {
            r = max(items.second, r);
        }
    }
}
int main() 
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin >> n;
    for (int i = 0; i < n; i++) {
        int l, r;
        cin >> l >> r;
        query.push_back({l, r});
    }
    
    sort(query.begin(), query.end());
    
    merge();
    
    cout << res;
    return 0;
}