Insert Interval.txt

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

struct Interval {
	int start;
	int end;
	Interval() : start(0), end(0) {}
	Interval(int s, int e) : start(s), end(e) {}
};

//using some other space
//vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) 
//{
//	vector<Interval> ret;
//	int n = intervals.size();
//	if(n == 0)
//	{
//		ret.push_back(newInterval);
//		return ret;
//	}
//	int i = 0;
//	while(i < n && intervals[i].end < newInterval.start)
//		ret.push_back(intervals[i++]);
//	while(i < n && newInterval.end >= intervals[i].start)
//	{
//		newInterval.end = max(intervals[i].end, newInterval.end);
//		newInterval.start = min(intervals[i].start, newInterval.start);
//		i++;
//	}
//	ret.push_back(newInterval);
//	while(i < n)
//		ret.push_back(intervals[i++]);
//	return ret;
//}


//do it in place
int findPos(vector<Interval> &intervals, Interval &newInterval)
{
	int start = 0;
	int end = intervals.size() - 1;
	while(start <= end)
	{
		int mid = (start + end) / 2;
		if(intervals[mid].start  == newInterval.start)
			return mid;
		else if(intervals[mid].start < newInterval.start)
			start  = mid + 1;
		else 
			end = mid - 1;
	}
	return start;
}

vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) 
{
	if(intervals.size() == 0)
	{
		intervals.push_back(newInterval);
		return intervals;
	}
	int pos = findPos(intervals, newInterval);
	intervals.insert(intervals.begin() + pos, newInterval);
	int i = 0;
	while(i < intervals.size()) //因为直接在intervals上增删，所以每次需重新调用size()
	{
		if(i < intervals.size() - 1 && intervals[i].end >= intervals[i + 1].start)
		{
			intervals[i].end = max(intervals[i].end, intervals[i + 1].end);
			intervals.erase(intervals.begin() + i + 1);
		}
		else
			++i;
	}
	return intervals;
}