区间合并(nlogn)
0–L个连续点,给定n个区间表示点的区间,将区间内的点去掉,求剩下点的个数
思路:
1.暴力做法:点的数量减去各区间内点的数量
2.区间合并:将所给区间按左端点排序
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int L, n;
vector<pair<int ,int>> ve;
int main()
{
cin >> L >> n;
while(n--)
{
int l, r;
cin >> l >> r;
ve.push_back({l,r});
}
sort(ve.begin(), ve.end());
int l = -2e9, r = -2e9; //维护一个当前区间
int sum = 0;
for(auto v : ve)
{
if(v.first > r) //该集合的左侧大于维护区间的右侧,说明无交集
{
if(l != -2e9) sum += (r - l + 1);
l = v.first, r = v.second; //更新区间
}
else //有交集,扩大当前维护的区间
{
r = max(v.second, r);
}
}
sum += r - l + 1; //不要忘记加上最后一次维护的区间的长度
cout << L + 1 - sum;
return 0;
}