题目描述

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

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

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

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

样例

输入样例：

5
1 2
2 4
5 6
7 8
7 9

输出样例：

3

思路

1. 将所有区间按左端点排序

2. 遍历所有区间 [L,R]

1）当前区间左端点的值 <= 上一个区间右端点的值——两个区间有交集，更新右端点 R=max(R,seg[i].y)

2）当前区间左端点的值 > 上一个区间右端点的值——两个区间没有交集，将左右端点更新

#include<iostream>
#include<cstring>
#include<algorithm>

#define x first
#define y second 

using namespace std;

const int N=100010;

typedef pair<int,int> PII;

int n;
PII seg[N];

int main(){
    cin >> n;
    for(int i = 0;i < n;i ++) cin >> seg[i].x >> seg[i].y;

    sort(seg, seg + n);

    int res = n;
    int l = seg[0].x,r = seg[0].y;//取第一个区间的左右端点

    for(int i = 1;i < n;i ++){//从第二个区间开始遍历
        if(seg[i].x <= r) {
            r = max(r, seg[i].y);
            res--;
        }
        else{
            l = seg[i].x;
            r = seg[i].y;
        }
    }
    cout << res << endl;
    return 0;
}