51 nod 1091 线段的重叠

爱被打了一巴掌 2022-06-16 12:46 136阅读 0赞

[1091 线段的重叠][1091]

基准时间限制： 1  秒 空间限制： 131072  KB

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

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

Input

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

Output

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

Input示例

5
    1 5
    2 4
    2 8
    3 7
    7 9

Output示例

题目解析：

51nod最大水题，这是一个简单贪心题，如果要是使用暴力直接来解题，时间复杂度O(n^2)数据是50000，明显超时，想一下就会发现可以不用双层循环，首先，先对数据进行排序，按照起点排，起点相同的时候按照终点排，然后用后面的最大的去减去前面的就可以得到最大值

代码：

#include<stdio.h>
    #include<algorithm>
    #include<cstring>
    #define maxn 50005
    using namespace std;
    typedef struct node
    {
        int start_;
        int end_;
    } stru;
    bool cmp(stru a,stru b)
    {
        if(a.start_!=b.start_)
            return a.start_<b.start_;
        else
            return a.end_<b.end_;
    }
    int main()
    {
        stru n[maxn];
        int T,i,j,ans,end;
        int left,right,max_=0;
        scanf("%d",&T);
        for(i=0; i<T; i++)
            scanf("%d%d",&n[i].start_,&n[i].end_);
        sort(n,n+T,cmp);
        end=n[0].end_;
        for(i=0; i<T-1; i++)
        {
            max_=max(max_,min(end,n[i+1].end_)-n[i+1].start_);
            end=max(end,n[i+1].end_);
        }
        printf("%d\n",max_);
        return 0;
    }

[1091]: http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1091