区间合并

Posted by 磊落 on May 11, 2020

区间合并

算法例题描述

    给定 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 <vector>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

const int N = 100010;

vector<PII> segs;

void merge(vector<PII> & segs)
{
    vector<PII> res;
    
    int st = -2e9, ed = -2e9;
    
    sort(segs.begin(), segs.end());
    
    for (auto seg : segs)
        if (ed < seg.first)
        {
            st = seg.first;
            ed = seg.second;
            if (st != -2e9) res.push_back({st, ed});  //不用考虑最后一个区间是否被加入
            
        }else
        {
            ed = max(ed, seg.second);
        }
    
    
    // if (st != -2e9) res.push_back({st, ed}); //需要考虑最后一个区间被加入
    segs = res;
    
}


int main()
{
    int n;
    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;
}
FEATURED TAGS