区间合并

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

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

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

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

输入格式

第一行包含整数 n。

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

输出格式

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

数据范围

1≤n≤100000,
−10^9≤li≤ri≤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
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<pair<int,int>> a,res;

int main(){
    int n;
    cin>>n;
    while(n--){
        int l,r;
        cin>>l>>r;
        a.push_back({l,r});
    }
    sort(a.begin(),a.end());
    int start=a[0].first;
    int end=a[0].second;
    for(auto i:a){
        if(end>=i.first&&end<i.second) end=i.second;
        if(end<i.first){
            res.push_back({start,end});
            start=i.first;
            end=i.second;
            /* 或者这样写
 			if(end<i.first){
            	res.push_back({start,end});
            	start=i.first;
            	end=i.second;
        	}
        	else if(end<i.second) end=i.second;
        	}
        	*/
    }
    res.push_back({start,end});  //将最后的结果加入数组
    cout<<res.size();
    return 0;
}