LeetCode | 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].

思路：

其实这个题目并不是很难，只不过非常麻烦，其实思路可以使用二分查找找到合适的位置，一定要明白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 合龙区间

题目：

相关推荐