首页 > 代码库 > Insert Interval
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].
思路：看了网上的解法，貌似直接遍历就行了。写了个二分查找的，不如直接遍历来得直观，作死了！
1 class Solution { 2 public: 3 vector<Interval> insert( vector<Interval> &intervals, Interval newInterval ) { 4 int start = binary_search( intervals, newInterval.start ); 5 if( start < 0 ) { start = 0; } 6 if( start < (int)intervals.size() && intervals[start].end < newInterval.start ) { ++start; } 7 if( start >= (int)intervals.size() ) { 8 intervals.push_back( newInterval ); 9 return intervals;10 }11 int end = binary_search( intervals, newInterval.end );12 if( end < 0 ) {13 intervals.insert( intervals.begin(), newInterval );14 return intervals;15 }16 if( start <= end ) {17 intervals[start].start = min( intervals[start].start, newInterval.start );18 intervals[start].end = max( intervals[end].end, newInterval.end );19 intervals.erase( intervals.begin()+start+1, intervals.begin()+end+1 );20 } else {21 intervals.insert( intervals.begin()+start, newInterval );22 }23 return intervals;24 }25 private:26 int binary_search( vector<Interval> &intervals, int val ) {27 int start = 0, end = (int)intervals.size()-1;28 while( start <= end ) {29 int middle = ( start + end ) / 2;30 if( intervals[middle].start == val ) { return middle; }31 if( intervals[middle].start < val ) {32 start = middle + 1;33 } else {34 end = middle - 1;35 }36 }37 return end;38 }39 };
Insert Interval
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。