企业官网建设流程全解析

区间的并

题目描述

给定NNN个区间，其中第iii个区间从数轴上的AiA_iAi​出发，到BiB_iBi​结束，请计算并输出这些区间一共覆盖了多长的数轴。

输入格式

第一行：单个整数NNN；
第二行到第N+1N+1N+1行：每行两个整数表示AiA_iAi​与BiB_iBi​。

输出格式

单个整数：表示所有区间并集的长度。

数据范围

• 对于 50% 的数据，1≤n≤10001 \le n \le 10001≤n≤1000，0≤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,000，0≤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) 存储区间。

注意：区间长度是右端点减左端点（因为覆盖的是连续实数轴，长度即差值）。

带注释的源代码（仅增加注释，未改动原逻辑）

#include<bits/stdc++.h>usingnamespacestd;intn;pair<int,int>p[300005];// 存储区间，first为左端点，second为右端点intans=0;intmain(){cin>>n;// 读入所有区间for(inti=1;i<=n;i++){cin>>p[i].first>>p[i].second;}// 按左端点从小到大排序sort(p+1,p+n+1);// 初始化当前合并区间为第一个区间ints=p[1].first;intt=p[1].second;// 从第二个区间开始合并for(inti=2;i<=n;i++){// 如果当前区间的左端点 <= 已合并区间的右端点，说明有重叠if(p[i].first<=t){// 更新右端点为较大值t=max(t,p[i].second);}else{// 否则，当前合并区间结束，累加其长度ans+=t-s;// 开始新的合并区间s=p[i].first;t=p[i].second;}}// 加上最后一个合并区间的长度cout<<ans+t-s;return0;}