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

One consideration is, the i-place method maybe slower than using extra space for the new vector. So I create a new vector res for result returned.

Linear scan, and keep updating newInterval until intervals[i].start is larger than newInterval.end.

	/**
	* Definition for an interval.
	* struct Interval {
	* int start;
	* int end;
	* Interval() : start(0), end(0) {}
	* Interval(int s, int e) : start(s), end(e) {}
	* };
	*/
	class Solution {
	public:
	vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
	vector<Interval> res;
	if(intervals.empty()){
	res.push_back(newInterval);
	return res;
	}
	int start=newInterval.start;
	int end=newInterval.end;
	int low=intervals[0].start;
	int high=intervals[0].end;
	int i=0;
	for(; i<intervals.size(); ++i){
	//
	if(intervals[i].start>end){
	res.push_back(newInterval);
	break;
	}
	if((start>=intervals[i].start && start<=intervals[i].end)||
	intervals[i].start>=start && intervals[i].end<=end ||
	end>=intervals[i].start && end<=intervals[i].end){
	start=min(start, intervals[i].start);
	end=max(end, intervals[i].end);
	newInterval.start=start;
	newInterval.end=end;
	continue;
	}
	res.push_back(intervals[i]);
	}
	if(i==intervals.size()){
	res.push_back(newInterval);
	}
	for(; i<intervals.size(); ++i){
	res.push_back(intervals[i]);
	}
	return res;
	}
	};

view raw Q57InsertInterval.cpp hosted with ❤ by GitHub