AcWing - 区间合并(贪心)
发布日期:2021-07-01 00:21:56
浏览次数:2
分类:技术文章
本文共 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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
很好
[***.229.124.182]2024年04月28日 08时18分40秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
Linux内核学习收获
2019-05-01
optirun执行错误的解决办法
2019-05-01
pycharm无法识别pyqt的问题
2019-05-01
STLPort 哈希表 hash_map/hash_multimap 删除速度慢
2019-05-01
deepin系统没有声音的解决方法
2019-05-01
python学习笔记
2019-05-01
Ant内置任务之replace
2019-05-01
Ant内置任务之tstamp
2019-05-01
Ant内置任务之whichresource
2019-05-01
Ant内置任务之touch
2019-05-01
Ant内置任务之truncate
2019-05-01
Ant内置任务之sync
2019-05-01
Ant内置任务之symlink
2019-05-01
Ant内置任务之sound
2019-05-01
Ant内置任务之typedef
2019-05-01
jface databinding:部分实现POJO对象的监测
2019-05-01