51 Nod 1091 线段的重叠

2017-09-24 19:51:41

writer：pprp

上一个题目就是关于线段重叠最大值，这个是找区间最长重合？

给你n个线段，然后让你在其中选择两条，使两条尽可能重合多一点

解决方法;

1、将所有线段进行排序，按照起点升序，终点降序的方法排序

2、找到一个对比区间，有两个操作

　　（1）如果区间在对比区间中，那么进行比较记录

　　（2）如果区间在对比区间之外，那么继续比较，并且更新对比区间，因为如果依然对比这个区间，相比当前的区间，原来的对比区间更加没有可能取得结果

代码如下：

#include <iostream>

#include <algorithm>

using namespace std;

const int maxn = ;

struct node

{

    int l, r;

} pprp[maxn];

bool cmp(const node & n1, const node &n2)

{

    if(n1.l < n2.l)

        return true;

    if(n1.l == n2.l && n1.r > n2.r)

        return true;

    return false;

}

int main()

{

    ios::sync_with_stdio(false);

    int num;

    cin >> num;

    for(int i =  ; i < num ; i++)

    {

        cin >> pprp[i].l >> pprp[i].r;

    }

    sort(pprp,pprp+num,cmp);

    node cp = pprp[];

    int ans = -;

    for(int i =  ; i < num ; i++)

    {

        if(cp.r >= pprp[i].r)

            ans = max(ans,pprp[i].r-pprp[i].l);

        else

        {

            ans = max(ans,cp.r-pprp[i].l);

            cp = pprp[i];

        }

    }

    if(ans == -)

        cout << "" << endl;

    else

        cout << ans << endl;

    return ;

}