当前位置: 首页 > news >正文

质监站网址德州网站建设优化

质监站网址,德州网站建设优化,电商美工接单平台,土耳其网站后缀直接上题目,不废话! 题目 给定 n 个区间 [l,r],要求合并所有有交集的区间。 注意如果在端点处相交,也算有交集。 输出合并完成后的区间个数。 例如:[1,3] 和 [2,6] 可以合并为一个区间 [1,6]。 输入格式 第一行包含整数 n。 接下来 n 行&am…

直接上题目,不废话! 

题目

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

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

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

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

输入格式
第一行包含整数 n。

接下来 n 行,每行包含两个整数 l 和 r。

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

数据范围

1≤n≤100000,
−10e9≤l≤r≤10e9
输入样例:

5
1 2
2 4
5 6
7 8
7 9


输出样例:

3

思路 

对于这n个区间,我们可以先用vector数组存放,然后再对左端点进行排序, 排完序后,后一个区间的左端点就一定大于等于前一个区间的左端点了,如图,蓝色是一个维护的区间,st和ed分别是维护区间的左右端点

相邻的两个区间只有这三种情况,绿色和红色可以归为一种,就是它的左端点小于等于蓝色的右端点,那我们的维护区间的右端点就要取(蓝色的右端点,对比区间的右端点)的最大值,当出现橙色这种情况就说明蓝色区间已经是一个答案区间了

代码 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;typedef pair <int,int> PII;
vector <PII> segs; //输入的初始区间数组int n;void merge(vector <PII> &segs)
{vector <PII> res; // 定义的答案区间数组sort(segs.begin(), segs.end()); //按左端点的大小排序int st = -2e9, ed = -2e9; //分别是维护区间的左右端点,取一个很小值,确保小于所有的有效值/*for (auto item:vec)不改变迭代对象的值,效果是利用item遍历并获得vec容器中的每一个值*/for (auto seg : segs){if (ed < seg.first) //维护区间的右端点和对比区间的左端点不相交就是已经是合并好了一个答案区间{if (ed != -2e9) //两个if(ed!=-2e9)是确保初始值不被加入到答案数组{res.push_back({ st,ed });}st = seg.first, ed = seg.second; //更新维护区间}else{ed = max(ed, seg.second);}}if(ed!=-2e9) //如果区间不为空,那么最后一个区间一定是一个独立的答案区间res.push_back({ st,ed });segs = res; 
}
int main()
{cin >> n;while (n--){int l, r;cin >> l >> r;segs.push_back({ l,r });}merge(segs);cout << segs.size() << endl;return 0;
}

http://www.khdw.cn/news/16320.html

相关文章:

  • 哪两个数字域名是做医疗信息网站的google推广技巧
  • 三里河网站建设公司网络营销比较好的企业
  • 湖北外贸网站设计制作市场调研的方法有哪些
  • 雄县网站建设aso优化方案
  • wordpress升级缓存深圳seo优化公司排名
  • 濮阳建网站李飞seo
  • 网站怎么做一盘优化排名网络推广策划方案
  • 开家网站建设培训班域名权重是什么意思
  • phpcms 网站访问统计钟南山今天感染新冠了
  • 最好网站制作工具天津网络推广公司
  • 网站备案是在哪个部门新冠疫情最新情况
  • 低价网站制作免费友链互换
  • 网站not found免费留电话号码的广告
  • 百度收录网站方法餐饮培训
  • 做视频网站了几百万收录优美的图片
  • web网站开发历史百度信息流账户搭建
  • 饿了么如何做网站推广seo关键词是怎么优化的
  • 优秀的html5网站厦门seo公司
  • 东莞微网站建设多少钱企业网络营销策划案例
  • 网络科技公司网站建设策划百度怎么发布自己的广告
  • 女孩和狗做网站百度一下百度搜索首页
  • 宣武做网站好看的seo网站
  • wordpress建立seo排名赚
  • 深圳企业网站建设服务中心淘宝关键词排名优化
  • 上海监狱门户网站深圳货拉拉
  • 旅游网站建设的目标是什么网络营销模式下品牌推广途径
  • 如何优化网站代码seo专业培训中心
  • 金融公司网站 html网络推广公司经营范围
  • 做购物网站骗人如何推广自己产品
  • 游戏网站设计首页关键词优化价格