803. 区间合并

曾经终败给现在 2023-09-29 13:55 12阅读 0赞

给定 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
    输出样例：
    3

完整代码

#include<iostream>
    #include<algorithm>
    #include<vector>
    
    using namespace std;
    
    typedef pair<int,int> PII;
    
    const int N = 100010;
    
    int n;
    vector<PII> segs;
    
    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}); //将最后一个区间合并的结果也放到res中去
        
        segs=res;
        
    }
    
    
    int main(){
        
        
        cin>>n;
        
        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;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，12人围观）

还没有评论，来说两句吧...

相关阅读

相关 56. 合并区间

56. 合并区间题干描述解题思路代码实现题干描述 [力扣入口][Link 1] 给出一个区间的集合，请合并所有重叠的区间。示例 1

朴灿烈づ我的快乐病毒、/ 2023年10月16日 15:42/ 0 赞/ 147 阅读

相关 56. 合并区间

打卡!!!每日一题今天这道题难度一般，主要是感觉挺好玩的，和大家分享一下。题目描述：[56. 合并区间][56.] > 以数组 intervals 表示若干个区间的集

拼搏现实的明天。/ 2023年10月11日 19:38/ 0 赞/ 81 阅读

相关 803. 区间合并

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

曾经终败给现在/ 2023年09月29日 13:55/ 0 赞/ 13 阅读

相关区间合并 AcWing 803. 区间合并

区间合并 AcWing 803. 区间合并原题链接 [AcWing 803. 区间合并][AcWing 803.] 算法标签区间合并贪心思路

古城微笑少年丶/ 2023年09月28日 11:32/ 0 赞/ 125 阅读

相关区间合并算法

算法:st,ed表示当前区间的左端点和右端点 1.将所有区间按左端点排序 2.扫描整个区间,扫描的过程中,将所有可能有交集的区间合并 (1)a区间在当前区间的内部:st和

港控/mmm°/ 2022年10月27日 01:40/ 0 赞/ 151 阅读

相关 56. 合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals\[i\] = \[starti, endi\] 。请你合并所有重叠的区间，并返回一个不重叠

快来打我*/ 2022年08月31日 07:19/ 0 赞/ 226 阅读

相关【leetcode】合并区间

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

超、凢脫俗/ 2022年03月08日 09:54/ 0 赞/ 286 阅读

相关合并区间

题目描述给出一个区间的集合，请合并所有重叠的区间。示例 1: 输入: [[1,3],[2,6],[8,10],[15,18]] 输出: [[1,6

傷城~/ 2022年01月22日 00:53/ 0 赞/ 289 阅读

相关 LeetCode：合并区间

给出一个区间的集合，请合并所有重叠的区间。 > 来源：力扣（LeetCode）链接：[https://leetcode-cn.com/problems/merge-inte

梦里梦外;/ 2021年11月16日 14:24/ 0 赞/ 345 阅读

相关 Acwing‘803. 区间合并

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

水深无声/ 2021年11月01日 04:26/ 0 赞/ 309 阅读