当前位置:网站首页>803. 区间合并(贪心)左端点、右端点排序均可
803. 区间合并(贪心)左端点、右端点排序均可
2022-08-10 18:23:00 【一条小小yu】
给定 nn 个区间 [li,ri][li,ri],要求合并所有有交集的区间。
注意如果在端点处相交,也算有交集。
输出合并完成后的区间个数。
例如:[1,3][1,3] 和 [2,6][2,6] 可以合并为一个区间 [1,6][1,6]。
输入格式
第一行包含整数 nn。
接下来 nn 行,每行包含两个整数 ll 和 rr。
输出格式
共一行,包含一个整数,表示合并区间完成后的区间个数。
数据范围
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 <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
struct Range
{
int l,r;
bool operator< (const Range&W)const
{
return l < W.l;
}
}range[N]; //重载小于号,使其以左端点进行排序
int main()
{
int n;
cin >> n;
for(int i = 0;i < n;i ++)
{
int l,r;
scanf("%d%d",&l,&r);
range[i] = {l,r};
}
sort(range,range + n);
int res = 1;
int maxr = range[0].r;
for(int i = 1;i < n;i ++)
{
if(range[i].l <= maxr) maxr = max(maxr,range[i].r);
else
{
res ++;
maxr = range[i].r;
}
}
cout << res << endl;
return 0;
}
右端点:
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 1e5 + 10;
struct Range
{
int l,r;
bool operator< (const Range&W)const
{
return r < W.r;
}
}range[N];
int main()
{
int n;
cin >> n;
for(int i = 0;i < n;i ++)
{
int l,r;
scanf("%d%d",&l,&r);
range[i] = {l,r};
}
sort(range,range + n);
int res = 1;
int maxl = range[n - 1].l;
for(int i = n - 2;i >= 0;i --)
{
if(range[i].r >= maxl) maxl = min(maxl,range[i].l);
else
{
res ++;
maxl = range[i].l;
}
}
cout << res << endl;
return 0;
}
边栏推荐
- 消息队列初见:一起聊聊引入系统mq 之后的问题
- 搭建自己的以图搜图系统 (一):10 行代码搞定以图搜图
- API 网关的功能
- FPGA工程师面试试题集锦71~80
- 【FAQ】【Push Kit】推送服务,回执配置一直报错、回执过期修改、怎么删除配置的回执
- FPGA工程师面试试题集锦101~110
- 【FAQ】OpenHarmony与HarmonyOS的有什么区别?
- 三星Galaxy Watch5产品图片流出 非Pro表款亦有蓝宝石加持
- Interview Question 04.12. Summation Path-dfs+Auxiliary Array Method
- 入门:人脸专集2 | 人脸关键点检测汇总(文末有相关文章链接)
猜你喜欢
Toronto Research Chemicals BTK甜味剂配方丨D-Abequose
【2011】【论文笔记】用THz-TDS观察水树——
钻石价格预测的ML全流程!从模型构建调优道部署应用!
企业即时通讯是什么?可以应用在哪些场景?
报告详解影响英特尔10/11/12代酷睿处理器的ÆPIC Leak安全漏洞
redis.exceptions.DataError: Invalid input of type: ‘dict‘. Convert to a byte, string or number first
从企业的视角来看,数据中台到底意味着什么?
2022-08-09 Study Notes day32-IO Stream
MSE 治理中心重磅升级-流量治理、数据库治理、同 AZ 优先
Toronto Research Chemicals霉菌毒素分析丨伏马菌素B2
随机推荐
Interface test advanced interface script using -apipost (pre/post execution script)
开发模式对测试的影响
MSE 治理中心重磅升级-流量治理、数据库治理、同 AZ 优先
网络拓扑管理
pip3升级到22.2.2
FFmpeg Huaping solution (modify source code, discard incomplete frames)
FPGA工程师面试试题集锦91~100
消息队列初见:一起聊聊引入系统mq 之后的问题
【快应用】如何使用命令打包快应用rpk
6-10 二分查找(20分)
shell运算详解,看这一篇就够了!
基于GAMS的电力系统优化分析
装饰者模式
「POJ 3666」Making the Grade 题解(两种做法)
【图像去雾】基于颜色衰减先验的图像去雾附matlab代码
H3C_堆叠(IRF)及链路聚合在项目中的综合应用
搭载2.8K 120Hz OLED华硕好屏 无畏Pro15 2022锐龙版屏开得胜
【FAQ】HarmonyOS ETS如何给组件设置边框
Redis命令---key篇 (超全)
Consul Introduction and Installation