首页 > 代码库 > [LeetCode] Insert Interval 二分搜索
[LeetCode] Insert Interval 二分搜索
Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).
You may assume that the intervals were initially sorted according to their start times.
Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].
This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].
Hide Tags
Array Sort 这题是给定一组区间，然后再有一个区间，把重叠的区间合并，合并后的区间输出。
思路1：
简单的想法便是顺序遍历，将新的区间加入后排序，然后合并重叠的，之前写过了这个。
思路2：
思路1 合并的只会操作一次，所以换一个，因为一组区间是有序的，所以可以试图找出合并的头、尾，这样便能够加速。为了快速定位合并的头尾，可以使用二分搜索。
我定义了一个二分搜索，用于查找一组区间中，按头比较，找出不大于target 的最大区间头的idx。
这样便有了大概的定位，然后把一组区间中做部分的加入返回，然后创造新的区间，加入返回，最后把剩余的后部区间加入返回。
需要注意的是创造区间有可能并不与其他合并，即 加入的区间 不和其他区间重叠，比较麻烦的是确定切割的地方。
#include <vector>#include <iostream>using namespace std;/** * Definition for an interval. */struct Interval { int start; int end; Interval() : start(0), end(0) {} Interval(int s, int e) : start(s), end(e) {}};class Solution {public: vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) { int n = intervals.size(); if(n<1) return vector<Interval>{{newInterval.start,newInterval.end}}; vector<Interval> ret;// if(n==1){// if(newInterval.end<intervals[0].start){// ret.push_back(newInterval); ret.push_back(intervals[0]);// return ret;// }// if(intervals[0].end<newInterval.start){// ret.push_back(intervals[0]); ret.push_back(newInterval);// return ret;// }// } int idx1 =binsearch(intervals,newInterval.start); int idx2 =binsearch(intervals,newInterval.end); int idx_tmp,newStart; if(intervals[idx1].end>=newInterval.start){ idx_tmp = idx1-1; newStart = intervals[idx1].start<newInterval.start?intervals[idx1].start:newInterval.start; } else{ idx_tmp=idx1; newStart = newInterval.start; } for(int i=0;i<=idx_tmp;i++) ret.push_back(intervals[i]); int newEnd; if(newInterval.end<intervals[idx2].start){ newEnd = newInterval.end; idx_tmp = idx2; } else{ newEnd = intervals[idx2].end>newInterval.end?intervals[idx2].end:newInterval.end; idx_tmp = idx2+1; } ret.push_back(Interval(newStart,newEnd)); for(int i=idx_tmp;i<n;i++) ret.push_back(intervals[i]); return ret; } int binsearch(vector<Interval> &ints,int target) { if(ints.size()==1) return 0; int lft = 0,rgt = ints.size()-1; if(ints[rgt].start<=target) return rgt; if(ints[lft].start>=target) return lft; int ret = 0; do{ int mid = (lft+rgt)/2; if(ints[mid].start>target) rgt=mid; else lft=mid; ret = lft; if(ints[ret+1].start>target) break; }while(lft+1<rgt); return ret; }};int main(){ vector<Interval> intervals{{1,2},{3,5},{6,7},{8,10},{12,16}};// vector<Interval> intervals{{1,2}};// cout<<intervals[0].start<<" "<<intervals[1].end<<endl; Interval newInterval(-1,0); Solution sol; vector<Interval> ret = sol.insert(intervals,newInterval); for(int i=0;i<ret.size();i++) cout<<ret[i].start<<" "<<ret[i].end<<endl; return 0;}
[LeetCode] Insert Interval 二分搜索
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。