区间的并题目描述给定NNN个区间其中第iii个区间从数轴上的AiA_iAi出发到BiB_iBi结束请计算并输出这些区间一共覆盖了多长的数轴。输入格式第一行单个整数NNN第二行到第N1N1N1行每行两个整数表示AiA_iAi与BiB_iBi。输出格式单个整数表示所有区间并集的长度。数据范围对于 50% 的数据1≤n≤10001 \le n \le 10001≤n≤10000≤ai≤bi≤1040 \le a_i \le b_i \le 10^40≤ai≤bi≤104对于 100% 的数据1≤n≤300,0001 \le n \le 300,0001≤n≤300,0000≤ai≤bi≤1090 \le a_i \le b_i \le 10^90≤ai≤bi≤109样例样例1输入3 10 12 1 3 2 5输出6说明区间为 [1,5] 和 [10,12]总长度 4 2 6。样例2输入2 10 20 1 100输出99我的题解这道题要求计算多个区间并集的总长度。常规思路是先将所有区间按左端点排序然后依次合并重叠或相邻的区间实际上只要当前区间的左端点小于等于已合并区间的右端点就说明有重叠可以合并并累加不重叠部分的长度。具体来说我先把第一个区间作为当前合并区间[s, t]然后从第二个区间开始遍历如果当前区间的左端点p[i].first小于等于t说明它与当前合并区间有重叠或相邻我更新t为两者右端点的较大值继续合并否则当前合并区间结束我将它的长度t - s累加到答案中然后以当前区间作为新的合并区间。最后遍历结束后再加上最后一个合并区间的长度。时间复杂度排序 O(N log N)遍历 O(N)总 O(N log N)N 最大 300000可行。空间复杂度O(N) 存储区间。注意区间长度是右端点减左端点因为覆盖的是连续实数轴长度即差值。带注释的源代码仅增加注释未改动原逻辑#includebits/stdc.husingnamespacestd;intn;pairint,intp[300005];// 存储区间first为左端点second为右端点intans0;intmain(){cinn;// 读入所有区间for(inti1;in;i){cinp[i].firstp[i].second;}// 按左端点从小到大排序sort(p1,pn1);// 初始化当前合并区间为第一个区间intsp[1].first;inttp[1].second;// 从第二个区间开始合并for(inti2;in;i){// 如果当前区间的左端点 已合并区间的右端点说明有重叠if(p[i].firstt){// 更新右端点为较大值tmax(t,p[i].second);}else{// 否则当前合并区间结束累加其长度anst-s;// 开始新的合并区间sp[i].first;tp[i].second;}}// 加上最后一个合并区间的长度coutanst-s;return0;}
