A21 排序 区间合并_哔哩哔哩_bilibili

#include<bits/stdc++.h>
using namespace std;
#define int long long

#define N 20005
struct line{    //线段
  int l,r;
  bool operator<(line &t){
    return l<t.l;
  }
}a[N];
int n,st,ed,sum;
//a[] 存储每条线段的起点,终点
//st  存储合并区间的起点
//ed  存储合并区间的终点
//sum 存储合并区间的长度

signed main(){
  scanf("%lld",&n);
  for(int i=1;i<=n;i++) 
    cin>>a[i].l>>a[i].r;
  sort(a+1,a+n+1); //按起点排序
  
  st=a[1].l; ed=a[1].r;
  sum+=a[1].r-a[1].l;
  for(int i=2; i<=n; i++){
    if(a[i].l<=ed){
      if(a[i].r<ed) //覆盖
        continue;
      else {        //重叠
        st=ed;
        ed=a[i].r;
        sum+=ed-st;
      }
    }
    else{           //相离
      st=a[i].l;
      ed=a[i].r;
      sum+=ed-st;
    }
  }
  cout<<sum<<endl;
  return 0;
}

$$\color{#0e90d2}\huge{\texttt{my blog}}$$

原题目链接

我们可以将

    ________
   |   __   |
   |  |  |  |
---------------->
   2  5  9  11

的重叠覆盖情况看成

    _____
   |   __|__
   |  |  |  |
---------------->
   2  5  9  11

所以，若我们将起点和终点按照从小到大的顺序排序，对答案不会产生影响

例如微调样例：

3

-1 1

2 11

5 9

和原样例答案一样，都可以看成

        __________
    _  |    ______|__
   | | |   |      |  |
------------------------>
  -1 1 2   5      9  11

所以，我们得到了一个解法：分别对起点和终点进行排序，循环加上每一条线段的长度，若与前一条线段重复减去重复部分

代码如下

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int main()
{
    int n;
    cin>>n;
    long long a[20001],b[20001],l=0;//a数组存储起点，b数组存储终点，l表示最终长度
    for(int i=0;i<n;i++)
        cin>>a[i]>>b[i];//输入
    sort(a,a+n);
    sort(b,b+n);//由于起点终点的顺序对答案不产生影响，对a数组和b数组进行排序
    for(int i=0;i<n;i++)
    {
        l+=b[i]-a[i];//加上当前线段长度
        if(i+1<n)//如果这条线段不是最后一条线段
            if(b[i]>a[i+1])//如果这条线段与前一条线段有重复
                l-=b[i]-a[i+1];//减去重复部分
    }
    cout<<l;//输出
    return 0;
}