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].
思路：
Insert Interval是Merge Intervals的一个延伸问题，先看看怎么Merge
Given a collection of intervals, merge all overlapping intervals.
For
example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].
1 vector<Interval> merge(vector<Interval> &intervals) { 2 if(intervals.size() <= 1) 3 return intervals; 4 5 vector<Interval> vres; 6 sort(intervals.begin(), intervals.end(), intvalcomp);//先对interval排序 7 Interval tmp(intervals[0]); 8 for(Interval it:intervals){ 9 if(tmp.start == it.start){ 10 tmp.end = it.end; 11 }else if(tmp.end >= it.start){//intervals有序，必然有tmp.start < it->start 12 if(tmp.end < it.end)//直接无视后者{[1,4],[2,3]} 13 tmp.end = it.end;//直接吞并后者{[1,3],[2,4]} 14 }else{ 15 vres.push_back(tmp);//不相交 16 tmp = it; 17 } 18 } 19 vres.push_back(tmp);//漏掉这句会fail{[1,4],[1,4]} 20 return vres; 21 } 22 23 bool intvalcomp(Interval a, Interval b){ 24 if(a.start == b.start) 25 return a.end < b.end; 26 else 27 return a.start < b.start; 28 }
现在有了这个Merge好了的不相交区间序列，怎么进行插入呢？新序列按照start排好序（start肯定是各不相同的），第一步我们先用二分找出有交集的序列片段的开始，这一点很像Search Insert Position，然后再往后处理。
【题解】【区间】【二分查找】【Leetcode】Insert Interval & Merge Intervals
原文：http://www.cnblogs.com/wei-li/p/InsertIntervalandMergeIntervals.html