一、算法
第一步：将区间按照左端点从小到大排序。
第二步：维护 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;
}
