精华内容
下载资源
问答
  • 区间合并

    2021-04-11 16:35:17
    什么是区间合并: 假如给定 n 个闭区间[ai,bi],其中i=1,2,…,n。任意两个相邻或相交的闭区间可以合并为一个闭区间。例如,[1,2]和[2,3]可以合并为[1,3],[1,3]和[2,4]可以合并为[1,4],但是[1,2] 和 [3,4] 不可以...

    什么是区间合并:
    假如给定 n 个闭区间[ai,bi],其中i=1,2,…,n。任意两个相邻或相交的闭区间可以合并为一个闭区间。例如,[1,2][2,3]可以合并为[1,3][1,3][2,4]可以合并为[1,4],但是[1,2][3,4] 不可以合并。

    在这里插入图片描述

    思路

    1. 按区间左端点排序

    2. 扫描整个区间,扫描过程中将所有有交集的区间合并,第i个区间与当前维护的区间的关系分三种情况:

      • 第i个区间在当前区间的内部,区间合并完以后左右端点st,ed不变
      • 第i个区间与当前区间有交集,但不在内部,区间合并完以后ed_cur=ed_new,区间延长
      • 第i个区间与当前区间没有交集,将当前维护的区间返回,更新维护的区间为第i个区间

    在这里插入图片描述

    题目描述

    给定 n 个区间 [li,ri],要求合并所有有交集的区间。
    注意如果在端点处相交,也算有交集。
    输出合并完成后的区间个数。
    例如:[1,3] 和 [2,6] 可以合并为一个区间 [1,6]。

    #include <iostream>
    #include <vector>
    #include <algorithm>
    
    using namespace std;
    
    typedef pair<int, int> PII;
    
    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;
    }
    
    int main(){
        
        int n;
        cin >> n;
        
        vector<PII> segs;
        for(int i = 0; i < n; i++){
            int l, r;
            cin >> l >> r;
            segs.push_back({l, r});
        }
        
        merge(segs);
        
        cout << segs.size() << endl;
        
        return 0;
    }
    
    

    在这里插入图片描述

    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 9,991
精华内容 3,996
关键字:

区间合并