AcWing 刷题日记——803. 区间合并

简介: AcWing803. 区间合并

题目描述

给定 n个区间 [li,ri],要求合并所有有交集的区间。

注意如果在端点处相交,也算有交集。

输出合并完成后的区间个数。

例如:[1,3][2,6] 可以合并为一个区间 [1,6]

输入格式

第一行包含整数 n

接下来 n 行,每行包含两个整数 lr

输出格式

共一行,包含一个整数,表示合并区间完成后的区间个数。

数据范围

1n100000,

10^9liri10^9,

大体思路

从题目上看,会给我们几个区间,要我们求合并之后,有多少个交集,端点处相交也算交集,那想一下,会出现几种情况?可能有部分相交(包括端点相交),一种是一个在另一个里面,最后一种是两个毫无交点:

合并区间.png

那这就是合并区间能遇到的所有情况,废话不多说,奉上代码:

#include<iostream>#include<vector>#include<algorithm>usingnamespacestd;
intn;
vector<pair<int, int>>sec;//用于存放区间的两个端点voidmerge(vector<pair<int, int>>&sec)
{
vector<pair<int, int>>res;//用于存放合并好的区间sort(sec.begin(), sec.end());//将区间内部进行排序,pair类型排序默认先先用第一个排序,当第一个数字相同时候在比较第二个intl=-2e9, r=-2e9;
//遍历一下数组,合并区间for (autoitme : sec)
    {
if (r<itme.first)//如果现在维护的区间的右端点是小于遍历到的左端点的时候,说明维护的区间和所有区间没有交集,进入进行下一步操作        {
if (l!=-2e9)res.push_back({ l,r });//当维护区间的左端点不是边界的时候,就将这个区间放入到合并区间的容器当中l=itme.first, r=itme.second;//更新维护区间        }
//如果不是小于,则说明区间有交集,合并区间,将维护区间的右端点进行更新elser=max(r, itme.second);//对比哪个大,然后进行更新区间    }
if (l!=-2e9)res.push_back({ l,r });//检查一下是否还有数组没有放进来,如果有就放进来sec=res;//将sec的内容更新成res的}
intmain()
{
cin>>n;
for (inti=0; i<n; i++)
    {
intl, r;
cin>>l>>r;
sec.push_back({ l,r });//将区间两个端点放入到容器当中    }
merge(sec);//合并区间cout<<sec.size() <<endl;
return0;
}
目录
打赏
0
0
0
0
2
分享
相关文章
C++ std::chrono库使用指南 (实现C++ 获取日期,时间戳,计时等功能)(三)
C++ std::chrono库使用指南 (实现C++ 获取日期,时间戳,计时等功能)
497 1
精选:15款顶尖Python知识图谱(关系网络)绘制工具,数据分析的强力助手
这里有15款免费工具推荐:NetworkX(Python基础),Graph-tool(C++速度),Graphviz(可视化库),ipycytoscape(Jupyter集成),ipydagred3,ipySigma(NetworkX + Web),Netwulf(交互式),nxviz(Matplotlib绑定),Py3plex(复杂网络分析),Py4cytoscape(Python+Cytoscape),pydot(Graphviz接口),PyGraphistry(GPU加速),python-igraph,pyvis(交互式图形),SNAP(大规模网络分析)。绘制和理解网络图从未如此简单!
841 0
基于ssm+vue.js+uniapp小程序的校园疫情防控系统附带文章和源代码部署视频讲解等
基于ssm+vue.js+uniapp小程序的校园疫情防控系统附带文章和源代码部署视频讲解等
63 0
[读书][笔记]WINDOWS PE权威指南《一》PE的原理和基础 之 第一章 环境搭建及简单破解(下)
[读书][笔记]WINDOWS PE权威指南《一》PE的原理和基础 之 第一章 环境搭建及简单破解(下)
287 0
不写一行代码,完成机器视觉算法的研发
xNN云平台面向普通的研发、质量、UED、运营等非算法专业的同学,也面向视觉与非视觉领域的算法同学,提供全自动的模型训练与模型压缩能力。同时配合专业的数据管理、数据标注、模型评测、端侧发布、云侧发布、数据监控等全套工程能力,使得用户能够在不写一行代码的情况下完成计算机视觉算法从数据准备到发布的研发全流程。
1832 0
不写一行代码,完成机器视觉算法的研发
在 Go 中如何使用 database/sql 来操作数据库
在 Go 中如何使用 database/sql 来操作数据库
408 0
Js 根据年月获取这月或者年的开始日期和结束日期
Js 根据年月获取这月或者年的开始日期和结束日期
249 0
登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问