题解：AcWing 5961 区间合并

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】AcWing5961. 区间合并 - AcWing题库【题目描述】给定n nn个闭区间[ a i , b i ] [a_i,b_i][ai​,bi​]其中i 1 , 2 , … , n i1,2,\dots,ni1,2,…,n。任意两个相邻或相交的闭区间可以合并为一个闭区间。例如[ 1 , 2 ] [1,2][1,2]和[ 2 , 3 ] [2,3][2,3]可以合并为[ 1 , 3 ] [1,3][1,3][ 1 , 3 ] [1,3][1,3]和[ 2 , 4 ] [2,4][2,4]可以合并为[ 1 , 4 ] [1,4][1,4]但是[ 1 , 2 ] [1,2][1,2]和[ 3 , 4 ] [3,4][3,4]不可以合并。我们的任务是判断这些区间是否可以最终合并为一个闭区间如果可以将这个闭区间输出否则输出no。【输入】第一行包含整数n nn表示区间数量。接下来n nn行每行包含两个整数a i a_iai​和b i b_ibi​表示一个给定区间为[ a i , b i ] [a_i,b_i][ai​,bi​]。【输出】输出一行如果这些区间最终可以合并为一个闭区间则输出这个闭区间的左右边界用单个空格隔开否则输出no。【输入样例】5 5 6 1 5 10 10 6 9 8 10【输出样例】1 10【代码详解】#includebits/stdc.husingnamespacestd;#defineN100005// 定义最大区间数量// 区间结构体structPair{intl;// 区间左端点intr;// 区间右端点};Pair a[N];// 存储所有区间Pair pm;// 合并后的总区间// 比较函数按区间左端点升序排序boolcmp(Pair a,Pair b){returna.lb.l;}intmain(){intn;// 区间数量cinn;// 输入所有区间for(inti1;in;i){cina[i].la[i].r;}// 按区间左端点排序sort(a1,a1n,cmp);// 初始化合并区间为第一个区间pma[1];// 尝试合并所有区间for(inti2;in;i){// 如果当前区间与合并区间有重叠if(a[i].lpm.r){// 扩展合并区间的右端点pm.rmax(a[i].r,pm.r);}else{// 如果无法合并输出no并结束程序coutno;return0;}}// 输出合并后的总区间coutpm.l pm.r;return0;}【运行结果】5 5 6 1 5 10 10 6 9 8 10 1 10