线段的重叠

男娘i 2022-06-12 06:44 269阅读 0赞

X轴上有N条线段，每条线段包括1个起点和终点。线段的重叠是这样来算的， 1020 1020和 1225 1225的重叠部分为 1220 1220。

给出N条线段的起点和终点，从中选出2条线段，这两条线段的重叠部分是最长的。输出这个最长的距离。如果没有重叠，输出0。

Input

第1行：线段的数量N(2 <= N <= 50000)。   
第2 - N + 1行：每行2个数，线段的起点和终点。(0 <= s , e <= 10^9)

Output

输出最长重复区间的长度。

Sample Input

5

1 5
    2 4
    2 8
    3 7
    7 9

#include<cstdio>
    #include<cmath>
    #include<cstring>
    #include<map>
    #include<set>
    #include<algorithm>
    using namespace std;
    struct A{
        int s,e;
    }f[50001];
    bool cmp(A x, A y)
    {
        if(x.s!=y.s)
            return x.s<y.s;
        return x.e>y.e;
    }
    int main()
    {
        int n;
        while(~scanf("%d",&n))
        {
            for(int i=0;i<n;i++)
                scanf("%d %d",&f[i].s,&f[i].e);
            sort(f,f+n,cmp);
            int s=f[0].s,e=f[0].e;
            int maxx=0,sum;
            for(int i=1;i<n;i++)
            {
                if(s<=f[i].s&&e<f[i].e)
                    sum=e-f[i].s;
                else if(s<=f[i].s&&e>=f[i].e)
                    sum=f[i].e-f[i].s;
                maxx=max(maxx,sum);
                if(e>=f[i].e)
                    continue;
                s=f[i].s;
                e=f[i].e;
            }
            printf("%d\n",maxx);
        }
        return 0;
    }

发表评论取消回复

表情：

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

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

相关阅读

相关线段重叠

述 X轴上有N条线段，每条线段包括1个起点和终点。线段的重叠是这样来算的，\[10 20\]和\[12 25\]的重叠部分为\[12 20\]。给出N条线段的起点和终点，

谁借莪１个温暖的怀抱￠/ 2024年02月18日 22:08/ 0 赞/ 36 阅读

相关不重叠的线段

X轴上有N条线段，每条线段有1个起点S和终点E。最多能够选出多少条互不重叠的线段。（注：起点或终点重叠，不算重叠）。例如：151523233636，可以选23233636，

布满荆棘的人生/ 2024年02月18日 22:08/ 0 赞/ 37 阅读

相关 Fragment重叠的解决办法

这个方法确实简单暴力该BUG在support-v4 24.0.0+以上官方已修复原文：[http://www.jianshu.com/p/c12a98a36b2b][h

客官°小女子只卖身不卖艺/ 2022年09月27日 12:30/ 0 赞/ 219 阅读

相关定位元素的重叠

上篇我已经说了，position的元素都是漂浮起来的，肯定会发生一些重叠的现象，但是到底是谁覆盖了谁，又是谁伤害了谁呢？嘻嘻，当然正常情况下有先来后到之分，不过是后来的覆盖先到

傷城~/ 2022年07月15日 02:00/ 0 赞/ 182 阅读

相关 51 nod 1091 线段的重叠

[1091 线段的重叠][1091] 基准时间限制： 1 秒空间限制： 131072 KB X轴上有N条线段，每条线段包括1个起点和终点。线段的

爱被打了一巴掌/ 2022年06月16日 12:46/ 0 赞/ 193 阅读

相关窗口重叠

书籍《CCF 中学生计算机程序设计》江涛等给定两个窗口左右上下的坐标，求重叠的面积。 //left right top bottom incl

Love The Way You Lie/ 2022年06月16日 02:36/ 0 赞/ 249 阅读

相关不重叠的线段

X轴上有N条线段，每条线段有1个起点S和终点E。最多能够选出多少条互不重叠的线段。（注：起点或终点重叠，不算重叠）。例如： 15 15 23 23 36 36，可以选 23

骑猪看日落/ 2022年06月12日 06:44/ 0 赞/ 204 阅读

相关线段的重叠

X轴上有N条线段，每条线段包括1个起点和终点。线段的重叠是这样来算的， 1020 1020和 1225 1225的重叠部分为 1220 1220。给出N条线段的起点和终点，

男娘i/ 2022年06月12日 06:44/ 0 赞/ 270 阅读

相关线段的重叠(贪心)

线段的重叠(贪心) 描述 X轴上有N条线段，每条线段包括1个起点和终点。线段的重叠是这样来算的，\[10 20\]和\[12 25\]的重叠部分为\[12 20\]。

ゞ浴缸里的玫瑰/ 2022年05月15日 03:12/ 0 赞/ 250 阅读

相关不重叠的线段(贪心)

不重叠的线段(贪心) X轴上有N条线段，每条线段有1个起点S和终点E。最多能够选出多少条互不重叠的线段。（注：起点或终点重叠，不算重叠）。例如：1515232336

﹏ヽ暗。殇╰゛Y/ 2022年05月15日 02:46/ 0 赞/ 230 阅读