AcWing 803. 区间合并
原题链接
简单
合并区间
输入样例
5
1 2
2 4
5 6
7 8
7 9
输出样例
3
代码
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
vector<pair<int, int >> loc, res;
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; i++)
{
int l, r;
scanf("%d%d", &l, &r);
loc.push_back({ l, r });
}
sort(loc.begin(), loc.end());
int st = -2e9, ed = -2e9;
for (auto it : loc)//遍历数组,临时数组名为it
{
if (ed < it.first)//不能合并
{
if (ed != -2e9)//不是第一个数组
res.push_back({ st,ed });
st = it.first;
ed = it.second;
}
else if(ed<it.second)//可以合并
ed = it.second;
}
if (st != -2e9 && ed != -2e9)//最后一个还没有放入数组中,同时保证数组不为空
res.push_back({ st,ed });
printf("%d", res.size());//输出res数组的大小
return 0;
}