我要招人

去企业版

首页 > 试题广场 >

在一维坐标轴上存在许多条线段，用最简单的算法找出重合长度最

[问答题]

在一维坐标轴上存在许多条线段，用最简单的算法找出重合长度最长得两条线段。比如线段 A（1,5）、B（2,8）、C（3,9），则 B 和 C 的重合长度最长，为 5。

推荐

倏宁

这个问题可以转换成一个动态规划问题：
比如我们想求Sn(Sn表示从求从第一个segment开始，总共有n个元素的子问题，求这个子问题的最大重合线段。)，首先我们要证明这是一个动态规划问题：
我们要求Sn问题的最大重合线段，那么它只有可能有两种来源：
（1）Sn-1问题的最大重合线段，即Sn的最大重合线段出自前n-1个线段；
（2）第n个线段Segment[n-1](注意：我是从0开始计数的，所以下标为n-1的就是第n个线段)和前n-1个线段的重合线段中最长的那一个。
所以，问题的解法如下：
（1）首先按照所有线段的end值对所有线段进行排序；
（2）递归的从后往前求解，比如求Sn的最大重合线段，先通过递归求出Sn-1的最大重合线段(tmpMaxSeg)，再求出Segment[n-1]和前n-1个线段的重合线段中最长的那一个(currMaxSeg)，比较tmpMaxSeg和currMaxSeg的长度，选出最长的作为Sn的返回值。
（3）注意：递归出口：size==2时，只有两个线段，通过简单比较就可以得出最大覆盖线段；
至于这块儿：是为了应对原本传入的线段数组的大小小于等于1的情况，算是边界条件处理了，不是递归的出口。
假如传入数组大小为3，递归执行到数组大小为2时就可以返回了。

#include <iostream>
#include <cstdlib>
#include <algorithm>
const int LEN = 3;
using namespace std;
struct segment
{
    int start;
    int end;
};
// assume a.end < b.end
segment commonSeg(const segment & a, const segment & b)
{
    segment CommonSeg;
    if(a.end < b.start)
    {
        CommonSeg.end = 0;
        CommonSeg.start = 0;
    }
    else
    {
        CommonSeg.end = a.end;
        CommonSeg.start = b.start;
    }
    return CommonSeg;
}
int findMaxSegment(int size, segment * Segment, segment & maxSeg)
{
    if(NULL == Segment)
    {
        cerr << "the segment array is NULL" << endl;
        return -1;
    }
    else if(1 == size)
    {
        maxSeg = Segment[0];
        return maxSeg.end-maxSeg.start;
    }
    else if(2 == size)
    {
        if(Segment[0].end <= Segment[1].start)
        {
            maxSeg.start = 0;
            maxSeg.end = 0;
            return maxSeg.end-maxSeg.start;
        }
        else
        {
            maxSeg.end = Segment[0].end;
            maxSeg.start = Segment[1].start;
            return maxSeg.end-maxSeg.start;
        }
    }
    else
    {
        segment tmpMaxSeg, tmpSeg,currMaxSeg;
        int currMaxLen = 0;
        findMaxSegment(size-1, Segment, tmpMaxSeg);
        for(int i=0; i<size-1; i++)
        {
            tmpSeg=commonSeg(Segment[i], Segment[size-1]);
            if(tmpSeg.end - tmpSeg.start > currMaxLen)
            {
                currMaxLen = tmpSeg.end - tmpSeg.start;
                currMaxSeg = tmpSeg;
            }
        }
        if(tmpMaxSeg.end - tmpMaxSeg.start > currMaxLen )
        {
            maxSeg = tmpMaxSeg;
        }
        else
        {
            maxSeg = currMaxSeg;
        }
        return maxSeg.end - maxSeg.start;
    }
}


bool isShorter(const segment & s1, const segment & s2)
{
    return s1.end < s2.end;
}
int main()
{
    segment * Segment = new segment[LEN];
    Segment[0].start = 1;
    Segment[0].end = 5;
    Segment[1].start = 2;
    Segment[1].end = 8;
    Segment[2].start = 3;
    Segment[2].end = 9;
    sort(Segment, Segment + LEN, isShorter);
    segment maxSeg;
    findMaxSegment(LEN, Segment, maxSeg);
    cout << maxSeg.start << endl;
    cout << maxSeg.end << endl;
    delete [] Segment;
    return 0;
}

编辑于 2015-02-02 11:56:09 回复(0)

张立超

//先将所以线段利用括号内的first值sort（利用map自动）一下，然后利用动态规划(简易版，偏向贪心)的思想找最长

int findLargestCommonPart(initializer_list<tuple<int, int> > il) {

if (il.size() == 0) return 0;

if (il.size() == 1) return get<1>(*il.begin()) - get<0>(*il.begin());

multimap<int, int> map;

for (auto it = il.begin(); it != il.end(); it++) {

//map[key] = value; //multimap没有[]

map.insert(pair<int, int>(get<0>(*it), get<1>(*it)));

}

auto itMap = map.begin();

int latEnd = itMap->second;

int largest = INT_MIN;

itMap++;

for (; itMap != map.end(); itMap++) {

if (latEnd - itMap->first >= largest) {

largest = latEnd - itMap->first;

latEnd = itMap->second;

}

return largest;

}

发表于 2016-08-28 09:54:10 回复(2)

woshi小k

思路：

①设A线段和B线段分别表示为(x_A,y_A)，(x_B,y_B)，则A线段和B线段重合的条件为y _A >x_B；

②遍历求两两线段的长度，找出最大值，时间复杂度为O(n²)，空间复杂度O(1)；

代码：

#include <iostream>

struct Line
{
	int x;
	int y;
};

void yanfa2012q5()
{
	Line lines[3];
	lines[0].x=1;
	lines[0].y=5;
	lines[1].x=2;
	lines[1].y=8;
	lines[2].x=3;
	lines[2].y=9;
	int length,maxLength=0;
	for (int i=0;i<3;i++)
	{
		for (int j=i+1;j<3;j++)
		{
			if (lines[i].y>lines[j].x)
			{
				//如果XB>XA,长度=YA-XB，否则长度=YA-XA
				length=lines[i].y-(lines[j].x>lines[i].x?lines[j].x:lines[i].x);
				if (length>maxLength||0==maxLength)
				{
					maxLength=length;
				}
			}
		}
	}
	std::cout<<"最大长度"<<maxLength<<std::endl;
}

发表于 2015-07-16 19:09:23 回复(0)

树枝

楼上的递归可行，但是这类问题更通用的是用线段树。

构建线段树后（O(log(Max - Min))），将所有线段依此插入线段树（O(N*log(Max-Min))），然后广度遍历该树，找第一个出现的cover不为1的节点以及其前驱和后继O(log(Max - Min))，然后将这三个节点的长度（若前驱或后继cover为0则不合并）合并即为最长。综上，时间复杂度为O(N * log(Max-Min))。

发表于 2015-09-11 10:07:02 回复(0)

提交观点

问题信息

百度查找

来自：百度2012研发工程师笔试卷

难度：

4条回答 56收藏 10433浏览

在一维坐标轴上存在许多条线段，用最简单的算法找出重合长度最

问题信息

热门推荐

相关试题

在一维坐标轴上存在许多条线段， 用最简单的算法找出重合长度最

问题信息

热门推荐

相关试题

在一维坐标轴上存在许多条线段，用最简单的算法找出重合长度最