题目背景

曹操平定北方以后，公元 208 年，率领大军南下，进攻刘表。他的人马还没有到荆州，刘表已经病死。他的儿子刘琮听到曹军声势浩大，吓破了胆，先派人求降了。

孙权任命周瑜为都督，拨给他三万水军，叫他同刘备协力抵抗曹操。

隆冬的十一月，天气突然回暖，刮起了东南风。

没想到东吴船队离开北岸大约二里距离，前面十条大船突然同时起火。火借风势，风助火威。十条火船，好比十条火龙一样，闯进曹军水寨。那里的船舰，都挤在一起，又躲不开，很快地都烧起来。一眨眼工夫，已经烧成一片火海。

曹操气急败坏的把你找来，要你钻入火海把连环线上着火的船只的长度统计出来！

题目描述

给定每个起火部分的起点和终点，请你求出燃烧位置的长度之和。

输入格式

第一行一个整数，表示起火的信息条数 n。
接下来 n 行，每行两个整数 a,b，表示一个着火位置的起点和终点（注意：左闭右开）。

输出格式

输出一行一个整数表示答案。

输入输出样例

输入 #1复制

3
-1 1
5 11
2 9

输出 #1复制

11

说明/提示

数据规模与约定

对于全部的测试点，保证 1≤n≤2×104，−231≤a<b<231，且答案小于 231。

以上是题目说明,下面是我的思路和代码

思路:

首先,我看到这个题目,上面显示算法标签是离散化,但我认为区间合并还是比较简单的;

首先,我们可以使用pair数组,将每一个区间的左右端点存入,然后进行根据每个区间的左端点进行排序,就可以得到从小到大排序的区间,例如:

原数组:

(1,3)   (7,11)  (5,9)  (4,6)  (6,8)

排序后数组:
(1,3)  (4,6) (5,9) (6,8) (7,11)

这样排完序后的数组,当前区间和下一个区间就只有两种关系, 相离(比如(1,3) (4,6)两个数组没有交集)和包含(比如(5,9)包含(4,8),  (6,8)与(7,11)存在交集)

这样我们只需将当前数组的右端点和下一个数组的左端点进行比较,如果是第一种关系,说明当前区间是一个独立的区间,把他摘出来,更换左右端点到下一个区间与第三个区间进行比较;如果是第二种关系,就只需将右端点改为这两个区间右端点的较大值即可,具体看代码.

代码:

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <vector>     //头文件不需这么多,个人习惯>_>

using namespace std;

typedef pair<int,int> PII;

vector<PII>  segs;

int merge(vector<PII>&segs){
    int sum=0;
    vector<PII> res; 
    int l=-2e9,r=-2e9;   //定义一个无效区间
    sort(segs.begin(),segs.end());         //排序数组
    for(auto itam:segs){
        if(r<itam.first){    //相离关系直接摘出更换左右端点
            if(l!=-2e9) res.push_back({l,r});     //if语句的意思是如果是第一个区间,直接存入
            l=itam.first;
            r=itam.second;   
        } 
        else r=max(r,itam.second);  //包含关系
    }
    if(l!=-2e9) res.push_back({l,r});   //存入最后一个区间
    for(auto p:res){
        sum+=p.second-p.first;   // 计算合并后每一个区间的长度,并求和
    }
    return sum;     //返回长度
} 
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        int a,b;
        cin>>a>>b;
        segs.push_back({a,b}); 
    }
    cout<<merge(segs)<<endl;
     
    return 0;
}