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].
类似以前的merge Intervals,只不过这里实际上是要将一个Interval插入到内部之后，然后再merge一下
而且这里的intervals在这里首先是已经排好序了的：
首先是一个带二分搜索的C++的方法：
1 class Solution { 2 public: 3 static bool comp(Interval a,Interval b){ 4 return a.start<b.start; 5 } 6 vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) { 7 if(intervals.size()==0){ 8 intervals.push_back(newInterval); 9 return intervals; 10 } 11 // sort(intervals.begin(),intervals.end(),comp); 12 if(intervals[0].start>newInterval.end){ 13 intervals.insert(intervals.begin(),newInterval); 14 return intervals; 15 } 16 else if(intervals[intervals.size()-1].end<newInterval.start){ 17 intervals.push_back(newInterval); 18 return intervals; 19 } 20 int left = binaryS(newInterval.start,intervals,0,intervals.size()-1, true); 21 int right = binaryS(newInterval.end, intervals,left, intervals.size()-1,false); 22 int delLeft,delRight; 23 cout<<left<<right; 24 if(left == 0 && intervals[0].start>newInterval.start){ 25 delLeft = left; 26 } 27 else if(intervals[left].end>= newInterval.start){ 28 newInterval.start = intervals[left].start; 29 delLeft = left; 30 } 31 else{ 32 delLeft = left+1; 33 } 34 35 if(right == intervals.size()-1 && intervals[right].end<newInterval.end){ 36 delRight = right; 37 } 38 else if(intervals[right].start<= newInterval.end){ 39 newInterval.end = intervals[right].end; 40 delRight = right; 41 } 42 else{ 43 delRight = right-1; 44 } 45 cout<<delLeft<<" "<<delRight<<endl; 46 vector<Interval> result; 47 48 for(int i=0;i<delLeft;i++){ 49 result.push_back(intervals[i]); 50 } 51 result.push_back(newInterval); 52 for(int i=delRight+1;i<intervals.size();i++){ 53 result.push_back(intervals[i]); 54 } 55 return result; 56 // for(int i=delLeft;i<=delRight;i++){ 57 // intervals.erase(intervals.begin()+delLeft); 58 // } 59 // intervals.push_back(newInterval); 60 // return intervals; 61 } 62 int binaryS(int x, vector<Interval> & intervals, int low, int high, bool isStart){ 63 if(isStart){ 64 65 66 while(low < high){ 67 int mid = (low + high +1 ) /2; 68 cout<<low<<high; 69 if(intervals[mid].start <= x){ 70 low = mid; 71 } 72 else{ 73 high = mid-1; 74 } 75 } 76 } 77 else{ 78 while(low < high){ 79 int mid = (low + high) /2; 80 // cout<<low<<high; 81 if(intervals[mid].end < x){ 82 low = mid+1; 83 } 84 else{ 85 high = mid; 86 } 87 } 88 } 89 return low; 90 } 91 };
java版本的代码如下所示：
1 /** 2 * Definition for an interval. 3 * public class Interval { 4 * int start; 5 * int end; 6 * Interval() { start = 0; end = 0; } 7 * Interval(int s, int e) { start = s; end = e; } 8 * } 9 */ 10 public class Solution { 11 public List<Interval> insert(List<Interval> intervals, Interval newInterval) { 12 List<Interval> ret = new ArrayList<Interval>(); 13 int sz = intervals.size(); 14 if(sz == 0){ 15 ret.add(newInterval); 16 return ret; 17 } 18 int prev = 0, next = 1; 19 while(next < sz){ 20 if(newInterval != null && intervals.get(prev).end >= newInterval.start){ 21 intervals.get(prev).end = Math.max(intervals.get(prev).end, newInterval.end); 22 newInterval = null; 23 }else if(newInterval == null){ 24 if(intervals.get(prev).end >= intervals.get(next).start){ 25 intervals.get(prev).end = Math.max(intervals.get(prev).end, intervals.get(next).end); 26 next++; 27 }else{ 28 ret.add(intervals.get(prev)); 29 prev = next; 30 next++; 31 } 32 }else{ 33 ret.add(intervals.get(prev)); 34 prev++; 35 next++; 36 } 37 } 38 intervals.get(prev).end = Math.max(intervals.get(prev).end, intervals.get(sz-1).end); 39 ret.add(intervals.get(prev)); 40 return ret; 41 } 42 }