写法一
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int n;
typedef pair<int, int> PII;
vector<PII> nums;
vector<PII> res;
int main()
{
scanf("%d", &n);
for(int i=0;i<n;i++)
{
int l,r;
scanf("%d%d", &l, &r);
nums.push_back({l,r});
}
sort(nums.begin(),nums.end()); //按区间左端点排序
int st=-2e9,ed=-2e9; //st代表区间开头,ed代表区间结尾
for(auto v:nums)
{
if(ed<v.first) //情况一:两个区间无法合并
{
if(ed!=-2e9) res.push_back({st,ed});//区间1放进res数组
st=v.first,ed=v.second; //维护区间2
}
//情况2:两个区间可以合并,且区间1不包含区间2,区间2不包含区间1
else if(ed<v.second)
{
ed=v.second; //区间合并
}
//实际上也有情况3:区间1包含区间2,此时不需要任何操作,可以省略
//排序过后不可能有区间2包含区间1
}
//考虑循环结束后的st,ed变量,此时的st,ed变量不需要继续维护,直接放入res数组中即可
//因为这是最后的一个序列,所以不可能继续进行合并
res.push_back({st,ed});
printf("%d\n",res.size());
return 0;
}
写法二
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
void merge(vector<PII> &segs)
{
vector<PII> res;
sort(segs.begin(), segs.end());
int st = -2e9, ed = -2e9;
for (auto seg : segs)
if (ed < seg.first)
{
if (st != -2e9) res.push_back({st, ed});
st = seg.first, ed = seg.second;
}
else ed = max(ed, seg.second);
if (st != -2e9) res.push_back({st, ed});
segs = res;
}
int main()
{
int n;
scanf("%d", &n);
vector<PII> segs;
for (int i = 0; i < n; i ++ )
{
int l, r;
scanf("%d%d", &l, &r);
segs.push_back({l, r});
}
merge(segs);
cout << segs.size() << endl;
return 0;
}