(算法)最长重叠线段或区间
算法 最长 线段 区间 重叠
2023-09-14 09:00:36 时间
题目:
X轴上有N条线段,每条线段包括1个起点和终点。线段的重叠是这样来算的,[10 20]和[12 25]的重叠部分为[12 20]。
给出N条线段的起点和终点,从中选出2条线段,这两条线段的重叠部分是最长的。输出这个最长的距离。如果没有重叠,输出0。
思路:
1、暴力计算
依次计算两两线段之间的重叠长度,但复杂度太高
2、动态规划
假设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 <iostream> #include <algorithm> #include <vector> using namespace std; typedef struct{ int start; int end; }segment; bool isShorter(const segment &s1,const segment &s2); int commonSegment(const segment &seg_a,const segment &seg_b); int findLongestSegment(const vector<segment> &segments,int size); int main() { int n; int start,end; 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 by segment.end // sort(segments.begin(),segments.end(),isShorter); int maxLen; maxLen=findLongestSegment(segments,n); cout<<"Longest Length:"<<maxLen<<endl; } return 0; } bool isShorter(const segment &s1,const segment &s2){ return s1.end<s2.end; } //assume seg_a.end<seg_b.end int commonSegment(const segment &seg_a,const segment &seg_b){ segment commonSeg; if(seg_a.end<seg_b.start || seg_a.start>seg_b.end){ commonSeg.start=0; commonSeg.end=0; } else{ commonSeg.start=max(seg_a.start,seg_b.start); commonSeg.end=min(seg_a.end,seg_b.end); } return commonSeg.end-commonSeg.start; } int findLongestSegment(const vector<segment> &segments,int size){ vector<int> lens(size+1); lens[0]=0; lens[1]=0; lens[2]=commonSegment(segments[0],segments[1]); int tmpLen; // size>2 // dynamic programming for(int i=3;i<=size;i++){ lens[i]=lens[i-1]; for(int j=0;j<i-1;j++){ tmpLen=commonSegment(segments[i-1],segments[j]); cout<<tmpLen<<endl; lens[i]=max(lens[i],tmpLen); } } for(int i=0;i<size+1;i++) cout<<lens[i]<<endl; return lens[size]; }
递归方法:
#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; 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 by segment.end //sort(segments.begin(),segments.end(),isShorter); segment maxSeg; int maxLen; maxLen=findLongestSegment(segments,n,maxSeg); cout<<"Longest Length:"<<maxLen<<endl; cout<<"start:"<<maxSeg.start<<endl; cout<<"end:"<<maxSeg.end<<endl; } return 0; } bool isShorter(const segment &s1,const segment &s2){ return s1.end<s2.end; } //assume seg_a.end<seg_b.end segment commonSegment(const segment &seg_a,const segment &seg_b){ segment commonSeg; if(seg_a.end<seg_b.start || seg_a.start>seg_b.end){ commonSeg.start=0; commonSeg.end=0; } else{ commonSeg.start=max(seg_a.start,seg_b.start); commonSeg.end=min(seg_a.end,seg_b.end); } return commonSeg; } int findLongestSegment(const vector<segment> &segments,int size,segment &maxSegment){ if(size<=1) return 0; if(size==2){ maxSegment=commonSegment(segments[0],segments[1]); return maxSegment.end-maxSegment.start; } // size>2 // recursive method int maxLen,tmpLen; segment tmpMaxSeg; maxLen=findLongestSegment(segments,size-1,tmpMaxSeg); maxSegment=tmpMaxSeg; // maxSegment=(maxSegment,commonSeg) segment commonSeg; for(int i=0;i<size-1;i++){ commonSeg=commonSegment(segments[i],segments[size-1]); tmpLen=commonSeg.end-commonSeg.start; if(tmpLen>maxLen){ maxLen=tmpLen; maxSegment=commonSeg; } } return maxSegment.end-maxSegment.start; }
运行结果:
相关文章
- 扩展kmp求最长回文子串_算法-字符串之最长回文子串
- ADRC算法Auto Disturbances Rejection control
- 最长上升子序列nlogn算法
- 最长上升子序列 LIS算法实现[通俗易懂]
- 密码发展史以及常用编码算法介绍
- 【Redis08】删除策略与逐出算法
- java算法刷题02——深度优先搜索与广度优先搜索
- a*算法最短路径_最长路径算法
- 全链路总结!推荐算法召回-粗排-精排
- 尤瓦尔·赫拉利 | 认识你自己,不要被算法操控
- 快速排序算法详解
- BAT面试算法进阶(2)- 无重复字符的最长子串(暴力法)
- BAT面试算法进阶(4)- 无重复字符的最长子串(滑动法优化+ASCII码法)
- Python人工智能:基于sklearn的随机森林分类算法实现方法
- BAT面试算法进阶(5)- 最长回文子串(方法一)
- 可定制算法和环境,这个开源强化学习框架火了
- 算法练习:动态规划(最长公共子串问题)
- 【算法】二分法 ② ( 排序数组中查找目标值 | 二分法的经典写法 | 在排序数组中查找元素的最后一个位置 | 二分法的通用模板 )
- 2023-04-03:如何使用滑动窗口算法和回溯算法解决亚马逊面试题——最长连续相同元素子序列问题?
- java归并排序算法代码详解编程语言