一、基础算法9：区间合并模板题+算法模板（区间合并）

傷城~ 2023-10-09 23:51 97阅读 0赞

#### 文章目录 ####

*  算法模板
 *   *  离散化题目模板
 *  模板题
 *   *  区间和
     *   *  原题链接
         *  题目
         *  题解
         *  思路

## 算法模板 ##

### 离散化题目模板 ###

// 将所有存在交集的区间合并
    void merge(vector<PII> &segs)
    {
        
        vector<PII> res;
    
        sort(segs.begin(), segs.end());
    
        int st = -2e9, ed = -2e9;
        for (auto seg : segs)
            if (ed < seg.first)
            {
        
                if (st != -2e9) res.push_back({
        st, ed});
                st = seg.first, ed = seg.second;
            }
            else ed = max(ed, seg.second);
    
        if (st != -2e9) res.push_back({
        st, ed});
    
        segs = res;
    }

## 模板题 ##

### 区间和 ###

#### 原题链接 ####

[https://www.acwing.com/problem/content/805/][https_www.acwing.com_problem_content_805]

#### 题目 ####

803 . 区间合并  
给定 n  
个区间 \[li,ri\]  
，要求合并所有有交集的区间。

注意如果在端点处相交，也算有交集。

输出合并完成后的区间个数。

例如：\[1,3\]  
和 \[2,6\]  
可以合并为一个区间 \[1,6\]  
。

输入格式  
第一行包含整数 n  
。

接下来 n  
行，每行包含两个整数 l  
和 r  
。

输出格式  
共一行，包含一个整数，表示合并区间完成后的区间个数。

数据范围  
1≤n≤100000  
,  
−109≤li≤ri≤109  
输入样例：

5
    1 2
    2 4
    5 6
    7 8
    7 9

输出样例：

#### 题解 ####

#include <iostream>
    #include <vector> 
    #include <algorithm>
    using namespace std;
    
    const int N = 1e5 + 10;
    
    typedef pair<int,int> PII;
    
    vector<PII> segs;
    
    int n,l,r;
    
    vector<PII> merge(vector<PII> segs){
        
    	vector<PII> res;
    	sort(segs.begin(),segs.end());
    	
    	int st = -2e9, ed = -2e9;
    	
    	for(auto seg : segs){
        
    		if(seg.first>ed){
        
    			if (st != -2e9) res.push_back({
        st,ed});
    			st = seg.first;
    			ed = seg.second;
    		}
    		else{
        
    //			ed = max(ed,seg.second);
    			if(seg.second > ed){
        
    				ed = seg.second;
    			}
    		}
    	}
    	if(st != -2e9) res.push_back({
        st,ed}); // 注意最后还要把最后一轮合并好的st,ed加进结果数组 
    	
    	return res; 
    }
    int main(){
        
    	cin>>n;
    	
    	for(int i=0;i<n;i++){
        
    		cin>>l>>r;
    		segs.push_back({
        l,r});
    	}
    	
    	vector<PII> res = merge(segs);
    
    	cout<< res.size() <<endl;
    	
    	return 0; 
    }

#### 思路 ####

![请添加图片描述][69b17fa7b8f840088cac514be57853af.png]  
按区间左端点排序，从左开始遍历  
有三种情况：设当前区间左右端点为(st,ed)  
① 新的区间st<st1<ed,ed1<ed,即在当前区间内，此时不用更新;  
②新的区间st<st2<ed,ed2>ed,此时需要更新右端点，即ed = ed2;  
③新的区间st3>ed,此时需要维护一个新的区间，将前面合并好的(st,ed)区间加入到结果vector中，然后st = st3,ed = ed3,维护该区间向后进行遍历；

[https_www.acwing.com_problem_content_805]: https://www.acwing.com/problem/content/805/
[69b17fa7b8f840088cac514be57853af.png]: https://img-blog.csdnimg.cn/69b17fa7b8f840088cac514be57853af.png