本文主要是介绍5.在一维坐标轴上有n个区间段，求重合区间最长的两个区间段。，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这种题目见过一些类似的题目。这里整理一下思路。
一位很牛逼的网友写的，点击打开链接。用的是分治法，类似于归并排序。
还有一种动态规划的方法，点击打开链接，思路如下：
假设S[n]表示n条线段中最长重叠距离，最长重叠距离只与两条线段有关，那么考虑两种情况：
1. 最长重叠距离与第n条线段无关，则最长重叠距离存在于前n-1条线段中，即S[n]=S[n-1]；
2. 最长重叠距离与第n条线段有关，则最长重叠距离为第n条线段与前面n-1条线段中的最大重叠距离者，S[n]=max(overlap(segment[n],segment[i])), i=1....n-1
因此得到状态转移方程：
S[n]=0; n<=1
S[2]=overlap(segment[0],segment[1])
S[n]=max(S[n-1],max(overlap(segment[n],segment[i])))
这里复习一下动态规划：点击打开链接
代码如下，原版抄的，自己水平真心有限
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;typedef struct{int start;int end;
}segment;bool isShorter(const segment &s1,const segment &s2);
segment commonSegment(const segment &seg_a,const segment &seg_b);
int findLongestSegment(const vector<segment> &segments,int size,segment &maxSegment);int main()
{int n;int start,end;cout<<" 输入线段个数"<<endl;while(cin>>n){vector<segment>segments(n);for(int i=0;i<n;++i){if(cin>>start && cin>>end){segments[i].start=start;segments[i].end=end;}}sort(segments.begin(),segments.end(),isShorter);segment maxSeg;int maxLen=findLongestSegment(segments,n,maxSeg);cout<<"Longest Length:"<<maxLen<<endl;cout<<"start:"<<maxSeg.start<<endl;cout<<"end:"<<maxSeg.end<<endl;}/*system("pause");*/return 0;
}bool isShorter(const segment &s1,const segment &s2){return s1.end<s2.end;
}segment commonSegment(const segment &seg_a,const segment &seg_b){segment commonSeg;if(seg_a.end < seg_b.start){commonSeg.start=0;commonSeg.end=0;}else{commonSeg.start=seg_b.start;commonSeg.end=seg_a.end;}return commonSeg;
}int findLongestSegment(const vector<segment> &segments,int size,segment &maxSegment){if(size <= 0)return 0;if(size == 1){maxSegment.start=segments[0].start;maxSegment.end=segments[0].end;return maxSegment.end-maxSegment.start; }if(size == 2){maxSegment = commonSegment(segments[0],segments[1]);return maxSegment.end-maxSegment.start;}//szie>2 动态规划int maxLen,tempLen;segment tempMaxSeg;maxLen = findLongestSegment(segments,size-1,tempMaxSeg); //递归maxSegment = tempMaxSeg; segment commonSeg;for(int i=0;i<size-1;++i){ //这里记得是size-1，链接中打错了commonSeg=commonSegment(segments[i],segments[size-1]);//只需比较最后一个和前面每一个的公共区间tempLen=commonSeg.end-commonSeg.start;if(tempLen > maxLen){maxLen= tempLen;maxSegment=commonSeg;}}return maxSegment.end-maxSegment.start;
}
这篇关于5.在一维坐标轴上有n个区间段，求重合区间最长的两个区间段。的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
