【刷题】基础算法——区间和并【模板】

【刷题】基础算法——区间和并【模板】

用贪心的思想，按区间左端点从小到大排序，从前到后扫描区间。

当前区间x和下一个区间和y的关系只有三种情况
1、y在x内： x r > y r x_r> y_r xr​>yr​且 x r > y l x_r>y_l xr​>yl​
|-------------------|
____|-------|
2、y与x没有交集： x r < y l x_r < y_l xr​ |-------------------|
________________|-------|
3、y与x有交集，但y不在x内： x r > y l x_r>y_l xr​>yl​且 x r < y r x_r |-------------------|
_________|-------|

可以看到有交集的充要条件是 x r > y l x_r>y_l xr​>yl​

不断维护区间的右端点，如果有交集（ x r > = y l x_r>=y_l xr​>=yl​），若 y r > x r y_r>x_r yr​>xr​，则更新 x r x_r xr​为更大的值 y r y_r yr​。
直到没有交集（ x r < y l x_r

#include 
#include 
#include 
using namespace std;

const int INF = 2e9;

struct node {
    int l, r;
}a[100005];

bool cmp(const node &x, const node &y) {
    return x.l < y.l;
}

vector> segs;

int n, ans;

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) {
        scanf("%d%d", &a[i].l, &a[i].r);
    }
    sort(a + 1, a + n + 1, cmp);
    int left = -INF, right = -INF;
    for (int i = 1; i <= n; i ++ ) {
        if (right >= a[i].l) {
            if (right < a[i].r) right = a[i].r;
        }
        else {
        	if(left != -INF) segs.push_back({left, right});
            left = a[i].l; right = a[i].r;
        }
        
    }
	if(left != -INF) segs.push_back({left, right});
    printf("%dn", segs.size());
    return 0;
}