一、算法

第一步：将区间按照左端点从小到大排序。
第二步：维护 a[i] 与 a[i+1] 这两个区间。
  ①如果a[i]和a[i+1]是有交集的：合并区间后赋值给a[i+1]。
  ②如果a[i]和a[i+1]没有交集：将a[i]区间放到结果数组中，然后继续将a[i+1]区间进行第二步。

二、代码

bool cmp(node a,node b) {
    return a.left < b.left;
}

void work() {
    sort(a,a+n,cmp);
    for(int i=0;i<n;i++) {
        if(a[i].right >=a[i+1].left && i+1<n) {//需要合并 
            a[i+1].left = a[i].left;
            a[i+1].right = max(a[i].right, a[i+1].right);
        } else {
            res[k++] = a[i];
        }
    }
} 

三、例题

1、题目：Acwing 422.校门外的树

2、代码

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

int L, n, k=0;//k是合并后区间的数目 

struct node {
    int left;
    int right;
};

node a[1005]; 
node res[1005];

bool cmp(node a,node b) {
    return a.left < b.left;
}

void work() {
    sort(a,a+n,cmp);
    for(int i=0;i<n;i++) {
        if(a[i].right >=a[i+1].left && i+1<n) {//需要合并 
            a[i+1].left = a[i].left;
            a[i+1].right = max(a[i].right, a[i+1].right);
        } else {
            res[k++] = a[i];
        }
    }
} 

int main(void) {
    cin >> L >> n;
    for(int i=0;i<n;i++) {
        cin >> a[i].left >> a[i].right;
    }
    work();//区间合并 
    int ans = L+1;
    for(int i=0;i<k;i++) {
        ans -= (res[i].right - res[i].left + 1);
    }
    cout << ans << endl;
    return 0;
} 

3、视频讲解

Acwing 422.校门外的树-视频讲解