扫二维码与项目经理沟通
我们在微信上24小时期待你的声音
解答本文疑问/技术咨询/运营咨询/技术建议/互联网交流
今天给大家讲解一下区间合并的题目；
给定 n个区间 [l,r][l,r]，要求合并所有有交集的区间。
注意如果在端点处相交，也算有交集。
输出合并完成后的区间个数。
例如：[1,3][1,3] 和 [2,6][2,6] 可以合并为一个区间 [1,6][1,6]。
输入格式
第一行包含整数 n。
接下来 n 行，每行包含两个整数 l 和 r。
输出格式
共一行，包含一个整数，表示合并区间完成后的区间个数。
数据范围
1≤n≤1000001≤n≤100000,
−109≤li≤ri≤109−109≤li≤ri≤109
输入样例：
5
1 2
2 4
5 6
7 8
7 9输出样例：
3然后我给大家讲解一下代码；讲解放在代码里；
#include
#include
#include
using namespace std;
typedef pair
void merge(vector
{
vector
sort(segs.begin(), segs.end());//排序；
int st = -2e9, ed = -2e9;//设定边界；
for (auto seg : segs)//进行遍历，C++11的特性；
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
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;
}
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
我们在微信上24小时期待你的声音
解答本文疑问/技术咨询/运营咨询/技术建议/互联网交流
微信二维码
移动版官网