AcWing 803. 区间合并
原题链接
简单
//区间合并
#include<iostream>
#include<vector>
#include<algorithm>
#define ll long long
using namespace std;
vector<pair<ll,ll>>num;//存区间边界
ll res;//保存区间数
int main()
{
int n;
cin >> n;
for(int i = 0;i < n;i++)
{
ll l,r;
cin >> l >> r;
num.push_back({l,r});
}
sort(num.begin(),num.end());//根据区间左边界排序
ll l = -2e9,r = -2e9;
/*选择一个输入区间不存在的范围,以防算了刚开始的区间*/
for(auto k:num)
{
if(r < k.first)
/*区间右边界小于后面一个区间左边界,即肯定不能有交集*/
{
if(l != -2e9)res++;//此区间可以直接计数
l = k.first,r = k.second;//更新使用区间情况
}
else if(r < k.second)
/*这个情况是一定有交集的,但是如果是左边那个区间将右边那个区间包含了,那么不能使用这个处理情况,因为这个方法是保存更新右边界,但是后面那个区间的右边界要小于原本的右边界,并且显然包含的情况可以不做改变*/
{
r = k.second;//更新右边界
}
}
res++;/*最后的区间在上一个for循环里面没有计算,因为那个循环还在继续判断后面是否有交集的区间,但是后面已经没有区间了,直接退出循环了,即没有再加这个区间数(极容易忘记)*/
cout << res << endl;
return 0;
}
//嘻嘻(●'◡'●)