嘎嘎嘎嘎嘎嘎嘎嘎嘎嘎嘎嘎嘎嘎嘎嘎嘎嘎嘎嘎嘎嘎嘎嘎嘎嘎嘎嘎嘎嘎嘎嘎

谢谢

贪心的代码，检查区间重合的三种情况和另外不重合的一种情况

当两个区间有重叠时：
1. 被另一段完全包含 -> 无意义，舍去
2. 右端点重合 -> 无意义，舍去
3. 右端点在区间外部，计算非重叠部分
4. 不重叠时，直接计算区间长度

前提是以贪心的思想，需要排序！

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

#define in inline
#define rint register int
typedef long long LL;
typedef pair<int,int> PII;

in int read()
{
    rint x=0,f=0; register char ch=getchar();
    while(ch<'0'||ch>'9')f|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return f?-x:x;
}

/*----------code----------*/
const int N=1e5+10;
PII a[N];
#define l first
#define r second
 
int n;

int main()
{
    n=read();
    for(int i=0;i<n;i++) a[i].l=read(),a[i].r=read();
    
    sort(a,a+n);
    
    int len=0;
    int last=a[0].l; //最右端的位置 
    for(int i=0;i<n;i++)
    {
        //这两种情况都要将last更新，因为另一个区间都在这个区间的右边！ 
        if(last>=a[i].l&&last<a[i].r) //有部分重叠 
        {
            len+=a[i].r-last;
            last=a[i].r;
        }
        else if(last<a[i].l) //不重叠 
        {
            len+=a[i].r-a[i].l;
            last=a[i].r;
        }
    }
    cout<<len;
    return 0;
}

这道题的题意有问题，依我的理解，答案应该是要求出连接每个船的锁链数。

因为如果用贪心的方法做这道题，样例的答案应该是13，也就是说我们求出的是区间覆盖的所有点数，但是答案是11。

所以只要把区间合并问题的模板稍作修改即可。