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的first一定是在一个区间的第二个位置上 merge的第二个坐标点一定是在某一个区间的第一个位置上，找到位置 ，根据找到的信息再判断怎么删除区间。
在开始之前，需要查看是否有特殊情况，就是在第一个插入 ，或者在最后一个插入。
#include <iostream>
#include <vector>
#include <string>
using namespace std;
void Insert_interval(vector<pair<int,int> >& interval,pair<int,int>& merge)
{
vector<pair<int,int> >::iterator itr;
int i;
int first =-1,second = -1;
if(interval[0].first >merge.second )
{
interval.push_back(merge);
swap(interval[0],interval[interval.size()-1]);
return ;
}
if(interval[interval.size()-1].second <merge.first)
{
interval.push_back(merge);
return ;
}
int begin=0,end = interval.size()-1;
while(begin <interval.size() && end >=0 )
{
if( first == -1)
{
if(interval[begin].first <=merge.first && interval[begin].second >= merge.first)
first = begin;
else if(interval[begin].first >=merge.first && interval[begin].second >= merge.first)
first = begin-1;
else
begin++;
}
if(second == -1)
{
if(interval[end].first <=merge.second && interval[end].second >= merge.second)
second = end;
else if(interval[end].first <=merge.first && interval[end].second <= merge.second)
second = end+1;
else
end--;
}
if(second !=-1 && first != -1)
break;
}
cout<<first<<" --- "<<second<<endl;
if(interval[first].first < merge.first && interval[first].second >merge.first)
interval[first].second = merge.first;
/*
else if(interval[first].first > merge.first && interval[first].second >merge.first)
{
interval[first-1].second = merge.first;
first--;
}
*/
if(interval[second].first<merge.second && interval[second].second > merge.second)
interval[second].first = merge.second;
interval.erase(interval.begin()+first+1,interval.begin()+second);
if(interval[first].second == merge.first && interval[first+1].first == merge.second)
{
interval[first].second =interval[first+1].second;
interval.erase(interval.begin()+first+1);
}
}
int main()
{
vector<pair<int,int> > interval;
pair<int,int> pa(1,2);
//pair<int,int> pa(1,3);
pair<int,int> pa1(3,5);
pair<int,int> pa2(6,9);
// pair<int,int> pa2(6,9);
pair<int,int> pa3(8,10);
pair<int,int> pa4(12,16);
interval.push_back(pa);
interval.push_back(pa1);
interval.push_back(pa2);
interval.push_back(pa3);
interval.push_back(pa4);
pair<int,int> merge(4,9);
Insert_interval(interval,merge);
int i;
return 0;
}LeetCode | Insert Interval 合并区间
原文：http://blog.csdn.net/yusiguyuan/article/details/44673691