AcWing - 区间合并(贪心)
发布日期:2021-07-01 00:21:56
浏览次数:3
分类:技术文章
本文共 1112 字,大约阅读时间需要 3 分钟。
题目链接:
时/空限制:1s / 64MB题目描述
给定 n 个区间 [li,ri],要求合并所有有交集的区间。
注意如果在端点处相交,也算有交集。
输出合并完成后的区间个数。
例如:[1,3]和[2,6]可以合并为一个区间[1,6]。
输入格式
第一行包含整数n。
接下来n行,每行包含两个整数 l 和 r。
输出格式
共一行,包含一个整数,表示合并区间完成后的区间个数。
数据范围
1≤n≤100000,
−10^9≤li≤ri≤10^9输入样例
5
1 2 2 4 5 6 7 8 7 9
输出样例
3
解题思路
题意:判断将n个区间可以合并成几个区间。
思路:我们可以先把区间按左端点从小到大排序,先按照第一个区间为标准,即相交区间,判断下一个区间和相交区间是否相交,如果不相交,则从下一个区间重新开始找,否则,就判断该相交区间能不能向右扩展,能的话就扩展,不能就算了,一直这样找就行了。Accepted Code:
/* * @Author: lzyws739307453 * @Language: C++ */#includeusing namespace std;const int MAXN = 100005;struct Interval { int l, r; bool operator < (const Interval &s) const { return s.l > l;//按照左端点从小到大排序 }}p[MAXN];int main() { int n; scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d%d", &p[i].l, &p[i].r); sort(p, p + n); int l = p[0].l, r = p[0].r, cnt = 1;//l, r分别是相交区间的左右端点 for (int i = 1; i < n; i++) { if (r < p[i].l) {//当新的左端点大于相交区间的右端点,则需要更新左右相交端点 cnt++; l = p[i].l, r = p[i].r;//重新更新相交区间 } else if (r < p[i].r)//相交,判断能不能向右扩展 r = p[i].r; } printf("%d\n", cnt); return 0;}
转载地址:https://lzyws739307453.blog.csdn.net/article/details/99938165 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
能坚持,总会有不一样的收获!
[***.219.124.196]2024年05月02日 01时44分38秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
c++中冒号(:)和双冒号(::)的用法【转】
2019-05-02
多个进程可以监听同一个端口?【转】
2019-05-02
Connection Refused的排查【转】
2019-05-02
只允许特定IP访问本网站的前端写法【转】
2019-05-02
Word页码从任意页开始设置方法
2019-05-02
更改Linux终端中用户名的显示颜色【转】
2019-05-02
Linux 套接字与文件描述符【转】
2019-05-02
Apache的MPM模式和httpd-mpm.conf【转】
2019-05-02
Apache 工作原理【转】
2019-05-02
mysql与mysqli的异同点【转】
2019-05-02
TR069协议向导——一个帮助你了解TR069协议的简明教程(一)【转】
2019-05-02
什么是BSS/OSS,及区别和联系【转】
2019-05-02
TR-069 协议完整的通信过程【转】
2019-05-02
Linux中/proc目录下文件详解【转】
2019-05-02
详解linux系统下/proc文件夹目录内容介绍【转】
2019-05-02
【OSGI】1.初识OSGI-到底什么是OSGI【转】
2019-05-02
LINUX驱动学习之什么是驱动?【转】
2019-05-02
TCP UDP 的区别和具体应用场景【转】
2019-05-02
tcp的2MSL问题【转】
2019-05-02