本文共 1646 字，大约阅读时间需要 5 分钟。

区间和并

区间和并就是将n个区间进行合并，有重叠部分的区间合并成一个新的区间，无重叠部分的区间保持独立，如下图：

上面的是原区间1、2、3、4，然后将所有的区间合并，就得到了下面的两个新区间（将1、2合并了）。这就是区间合并问题。

思路

那么，知道了区间和并是什么之后，我们如何实现合并呢？这里我们可以先对左端点排个序，然后用一个l，r来维护当前区间，①若下一个区间的l <= 当前维护的区间的右端点r，那么我们就将当前区间的r修改成max(r , 下一个区间的r)，这里一定是取两者的最大值，因为可能存在上图2、3区间的情况，下一个区间被当前区间包含了。②若下一个区间的l > 当前维护的区间的右端点r，那么我们当前维护的区间[l,r]就是一个单独的区间了，恶魔将这个区间存入数组中，然后将l和r更新为下一个区间的左右端点，然后重复上述操作即可。这里的一个区间我们用结构体来存，同样我们也可以使用来存。

代码模板

#include
   
    #include
    
     #include
     
      using namespace std;typedef pair
      
        PII;PII a[110];	//用pair来存一个区间int n;vector
       
         ans;int main(){
   	cin >> n;	for(int i = 0;i < n;i++)		cin >> a[i].first >> a[i].second;	sort(a,a+n);	//按左端点排序	int l = a[0].first,r = a[0].second;	//l和r就是用来维护的当前区间的左右端点，初始化为第一个区间	for(int i = 1;i < n;i++)	{
   		if(a[i].first <= r)	//第一种情况			r = max(r,a[i].second);		else			//第二种情况		{
   			ans.push_back({
   l,r});			l = a[i].first;			r = a[i].second;		}	}	ans.push_back({
   l,r});	//别忘了把最后一个区间[l,r]也存进去	return 0;}
       
      
     
    
   

经典例题

NOIP2005普及组：

题目大意

一共有n个点，给出m个区间，求区间合并后的长度

思路

暴力想法：给区间内的每个点一个值，0或者1，全部初始化为1，然后循环每个区间，将区间内的每个点都记为0，然后看所有点为0的个数就是合并后区间的长度。时间复杂度O(nm)。

代码模板

#include
   
    #include
    
     using namespace std;pair
     
       a[110];int n,m;int main(){
   	cin >> n >> m;	for(int i = 0;i < m;i++)		cin >> a[i].first >> a[i].second;	sort(a,a+m);	int l = a[0].first,r = a[0].second,sum = 0;	for(int i = 1;i < m;i++)	{
   		if(a[i].first <= r)			r = max(r,a[i].second);		else		{
   			sum += r-l+1;			l = a[i].first;			r = a[i].second;		}	}	sum += r-l+1;	cout << n+1-sum << endl;		return 0;}
     
    
   

转载地址：http://mfbki.baihongyu.com/