nefu 1144 线段重叠

Description

在一维坐标轴中,给你N条线段,每条线段的起点和终点都是坐标轴上的整数点。例如,[10 29]和[12 25]的重叠部分为[12 25]。给出N条线段的起点(整数)和终点(整数),从中选择两条线段,使这两条线段的重叠部分是最长的。输出这个最长的距离。如果没有重叠,输出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

Sample Output

4

//这道题是贪心思想,不断更新最长线段的右区间;
#include <iostream>
#include <algorithm>
#include<cstdio>
using namespace std;

struct node
{
    int x,y;
} data[500005];

bool cmp(const node &a,const node &b)
{
    if(a.x<b.x) return true;
    else if(a.x==b.x)
    {
        if(a.y<b.y) return true;
        else return false;
    }
    else return false;
}

int main()
{
    int n,maxx;
    while(cin>>n)
    {
        maxx=0;
        for(int i=0;i<n;i++)
        scanf("%d%d",&data[i].x,&data[i].y);
        sort(data,data+n,cmp);
        int tmp=data[0].y,k;
        for(int i=1;i<n;i++)
        {
            if(data[i].y>=tmp)
            {
                maxx=max(maxx,tmp-data[i].x);
                tmp=data[i].y;
            }
            else maxx=max(maxx,data[i].y-data[i].x);
        }
        printf("%d\n",maxx);
    }
    return 0;
}
时间: 04-25

nefu 1144 线段重叠的相关文章

软件项目技术点(25)——提升性能之检测绘制范围

软件里的一个画面包含很多个元素,但是当缩放到某个局部位置时,需要绘制的元素个数就很少.那么怎么判断某个元素是否需要进行绘制呢? 我们在绘制整个画面时,是进行循环遍历每个元素的,如下判断是否进行绘制的代码: 1 var elements = this.commonElements.all();//获取所有元素列表 2 var winInfo = getWindow();//获取画布窗口的宽高值 3 var viewMinx = 0; 4 var viewMiny = 0; 5 var viewMa

线段的重叠(贪心)

题目:http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1091 先按线段起点升序排序,此时有两大种情况: 第一种是第二根线段的左边在第一根线段右边的右边, 即两根线段不相交,此时要将终点更新,因为是按起点升序排序,如果第二根的就不相交那之后的线段都不相交: 第二种大情况是相交,其第一种小情况是包含,此时要将重叠长度与最大重叠比较,但不需要更新终点, 第二种小情况是相交但不包含,此时不仅要比较最大重叠长度,还需要更新终点.

(算法)最长重叠线段或区间

题目: X轴上有N条线段,每条线段包括1个起点和终点.线段的重叠是这样来算的,[10 20]和[12 25]的重叠部分为[12 20]. 给出N条线段的起点和终点,从中选出2条线段,这两条线段的重叠部分是最长的.输出这个最长的距离.如果没有重叠,输出0. 思路: 1.暴力计算 依次计算两两线段之间的重叠长度,但复杂度太高 2.动态规划 假设S[n]表示n条线段中最长重叠距离,最长重叠距离只与两条线段有关,那么考虑两种情况: 1. 最长重叠距离与第n条线段无关,则最长重叠距离存在于前n-1条线段中

不重叠的线段

X轴上有N条线段,每条线段有1个起点S和终点E.最多能够选出多少条互不重叠的线段.(注:起点或终点重叠,不算重叠). 例如:[1 5][2 3][3 6],可以选[2 3][3 6],这2条线段互不重叠. 思路:贪心,就是以前的安排节目的题目,在这里将线段末端点按照从小到大排序,就跟哪个活动结束早哪个先安排 #include <iostream> #include <cstdio> #include <algorithm> #include <string>

11402 - Ahoy, Pirates!(线段树区间更新(标记重叠的处理))

题目链接:点击打开链接 题意:有3种区间操作, 将某个区间全部变成1: 将某个区间全部变成0:将某个区间的1变成0, 0变成1. 思路:前两个操作就是最基本的区间更新, 用到懒惰标记, 然而第3个操作却有些麻烦, 如果仅仅更新当前这个结点对应的大区间, 那么它所包含的小区间再次更新时就会发生错误, 错误的原因是因为标记的重叠和碰撞.  显然 , 这就是很典型的一个问题, 处理标记碰撞的问题. 问题的核心是解决碰撞, 使得每个点每个时刻至多只有一个标记. 那么怎么办呢?我们可以在两个标记发生碰撞的

hdu1542 Atlantis(扫描线+线段树+离散)矩形相交面积

题目链接:点击打开链接 题目描写叙述:给定一些矩形,求这些矩形的总面积.假设有重叠.仅仅算一次 解题思路:扫描线+线段树+离散(代码从上往下扫描) 代码: #include<cstdio> #include <algorithm> #define MAXN 110 #define LL ((rt<<1)+1) #define RR ((rt<<1)+2) using namespace std; int n; struct segment{ double l

POJ 1177:线段树 离散化 扫描线

计算畸形区域的周长 比面积的扫描要麻烦些,原因就在不重叠区域的处理,同一段高度可能要重复叠加 所以线段树的结点里要多维护三个东西: times:区间里不重叠的区间数 比如说第一个区间是1~5,第二个是2~6,,第三个是9~10,那前两个可以合成1~6,和第三个独立,则这个整体的times为2 为了维护times,我们需要lbd和rbd两个变量,分别作为区间左右端点是否被覆盖的标志 有的博客里把这两个变量写成了bool型,这些其实不好,在运算时会带来麻烦,我们直接用int 0和1表示会好些.这样只

HDOJ 5338 ZZX and Permutations 线段树+树状数组

[题意]: 给一个排列加上表示循环的括号,问如何让1到n的对应的字典序最大. 从1开始贪心每个数字可以往三个地方走,右边第一个,跳转到左边的某一个,和自己构成循环 对于走到右边第一个的情况,只要判断右边的那个有没有被占据就可以了,如果可以和右边的互换,那么需要在线段树中将右边的数置为0 跳转到左边的某一个,一个数如果跳转到左边的某一个则说明左边的那个是括号开头这个数是括号结尾,用一个线段树查询区间里的最大值,由于括号间是不能重叠的,所以需要用树状数组二分一下左边界.如果这个数是要跳转到左边的某个

HDU 4419 Colourful Rectangle --离散化+线段树扫描线

题意: 有三种颜色的矩形n个,不同颜色的矩形重叠会生成不同的颜色,总共有R,G,B,RG,RB,GB,RGB 7种颜色,问7种颜色每种颜色的面积. 解法: 很容易想到线段树扫描线求矩形面积并,但是如何维护每种颜色的长度着实让我伤透了脑筋.后来看了一位朋友的题解,才幡然醒悟. 开始想到了用二进制表示颜色,R用001表示,G用010表示,B用100表示.那么就可以用十进制1~7表示7种不同颜色了. 维护 cov[rt][1~3] 表示此区间内3种原色各有多少个, Len[rt][i]表示每种颜色的长