首页 > 代码库 > [LeetCode]Insert Interval 考虑多种情况
[LeetCode]Insert Interval 考虑多种情况
写太复杂了。
思想:确定带插入区间的每个边界位于给定区间中的哪个位置,共有5种情况
-1 |(0)_1_(2)| (3)
其中,0,1,2这三种情况是一样的。
确定每个带插入区间的两个边界分别属于哪种情况,记为flag0和flag1。
然后根据flag0和flag1的组合情况,分9种情况进行讨论
class Solution { public: vector<Interval> insert(vector<Interval> &its, Interval ni) { int i,n=its.size(),j,k; int flag0=-1,flag1=-1; vector<Interval>ans; if(n==0){ ans.push_back(ni); return ans; } for(i=0;i<n;++i) if((i==0||its[i-1].end<ni.start)&&its[i].start>ni.end) break; if(i<n||(i==n&&its[n-1].end<ni.start)){ for(k=0;k<i;++k)ans.push_back(its[k]); ans.push_back(ni); for(;k<n;++k)ans.push_back(its[k]); return ans; } for(i=0;i<n;++i){ if(its[i].end==ni.start){flag0=2;break;} else if(its[i].start==ni.start){flag0=0;break;} else if(its[i].start>ni.start)break; else if(its[i].start<ni.start&&its[i].end>ni.start){flag0=1;break;} } if(i==n&&flag0==-1)flag0=3;//no exist for(j=i;j<n;++j){ if(its[j].end==ni.end){flag1=2;break;} else if(its[j].start==ni.end){flag1=0;break;} else if(its[j].start>ni.end)break; else if(its[j].start<ni.end&&its[j].end>ni.end){flag1=1;break;} } if(j==n&&flag1==-1)flag1=3;//可能存在 for(k=0;k<i;++k)ans.push_back(its[k]); if(flag1==-1){ if(flag0==3){ ans.push_back(ni); return ans; } else if(flag0>=0&&flag0<=2){ its[i].end=ni.end; } else if(flag0==-1){ its[i].end=ni.end;its[i].start=ni.start; } ans.push_back(its[i]); for(k=j;k<n;++k)ans.push_back(its[k]); } else if(flag1>=0&&flag1<=2){ if(flag0==3){ its[j].start=ni.start; } else if(flag0>=0&&flag0<=2){ if(i!=j){ its[i].end=its[j].end; ans.push_back(its[i]); for(k=j+1;k<n;++k)ans.push_back(its[k]); return ans; } } else if(flag0==-1){ if(i==j){ its[j].start=ni.start; } else{ its[i].start=ni.start; its[i].end=its[j].end; ans.push_back(its[i]); for(k=j+1;k<n;++k)ans.push_back(its[k]); return ans; } } for(k=i;k<n;++k)ans.push_back(its[k]); } else if(flag1==3){//j==n if(flag0==3){ ans.push_back(Interval(-1117,-1117));//不存在 } else if(flag0>=0&&flag0<=2){ its[i].end=ni.end; ans.push_back(its[i]); return ans; } else if(flag0==-1){ its[i].start=ni.start; its[i].end=ni.end; ans.push_back(its[i]);return ans; } for(k=i;k<n;++k)ans.push_back(its[k]); } return ans; } };
[LeetCode]Insert Interval 考虑多种情况
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。