Problem
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
Given intervals
[1,3],[6,9]
, insert and merge [2,5]
in as [1,5],[6,9]
.
Example 2:
Given
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]
.Code
int find_l(const vector<Interval> &intervals,int n,int x) { int l = 1,r = n; while(l <= r){ int m = (l + r)/2; if(x < intervals[m - 1].start) r = m - 1; else if(x > intervals[m - 1].end) l = m + 1; else return (m - 2); } if(l == n + 1) return n - 1; else if( r == 0) return -1; else if(x > intervals[l - 1].end) return l - 1; else if(x < intervals[r - 1].start) return r - 2; return r - 1; } int find_r(const vector<Interval> &intervals,int n,int x) { int l = 1,r = n; while(l <= r){ int m = (l + r)/2; if(x < intervals[m - 1].start) r = m - 1; else if(x > intervals[m - 1].end) l = m + 1; else return (m); } if(l == n + 1) return n; else if( r == 0) return 0; else if(x > intervals[l - 1].end) return l; else if(x < intervals[r - 1].start) return r - 1; return r; } vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) { // IMPORTANT: Please reset any member data you declared, as // the same Solution instance will be reused for each test case. vector<Interval> result; int n = intervals.size(); int l = find_l(intervals,n,newInterval.start); int r = find_r(intervals,n,newInterval.end); for(int i = 0; i <= l; ++i) result.push_back(intervals[i]); if(r == l + 1){ result.push_back(Interval(newInterval.start,newInterval.end)); } else{ int left,right; if(l == n-1) left = newInterval.start; else left = min(newInterval.start,intervals[l + 1].start); if(r == 0) right = newInterval.end; else right = max(newInterval.end,intervals[r - 1].end); result.push_back(Interval(left,right)); } for(int i = r; i < n; ++i) result.push_back(intervals[i]); return result;}
No comments:
Post a Comment