【2021.2.13】区间合并——半有序区间
思路:
- 给定所有区间,记做[l, r], 先对所有区间按照l的大小进行排序
- 遍历排序后的每一个区间,依次前后判断相邻的两个区间,记做[x1, y1]和[x2,y2],因为按照第一个坐标排序,所以恒有x1<=x2,因此这两个区间是否有交集,取决于y1和x2的取值比较:
(1)如果y1>=x2,则这两个区间一定相交,合并的起始坐标我们可以不用管了(因为始终有序),因此合后的区间的末端点则取决于y1和y2取值,末端点end=max(y1, y2)。
(2)如果y1<x2,则前一个区间一定与后一个没有交集,也保证了其一定不会和后面所有的区间没有交集
注:算法实现中,每次合并一个区间,并将该区间与下一个区间进行判断是否合并,不断累积合并的末端值,如果可以合并,则记录一次,最终剩余合并的区间个数等于原始区间数减去合并的次数。
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 1e5 + 5;
int n, l, r;
vector<pair<int, int>> span;
static bool temp(pair<int, int> x, pair<int, int> y) {
return x.first < y.first;
}
int main() {
scanf("%d", &n);
int t = n;
while(t --) {
scanf("%d%d", &l, &r);
span.push_back({l, r});
}
sort(span.begin(), span.end(), temp);
int res = 0, end = span[0].second;
for(int i = 0; i < span.size() - 1; i ++) {
if(end >= span[i + 1].first) {
res ++;
end = max(end, span[i + 1].second);
}else {
end = span[i + 1].second;
}
}
printf("%d", n - res);
return 0;
}