merge intervals@leetcode

微博：http://www.weibo.com/cathyhwzn

刷题必备书籍：Cracking the Coding Interview: 150 Programming Questions and Solutions

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

	/**
	* 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>::iterator it=intervals.begin();
	while(it!=intervals.end())
	{
	if(newInterval.end<it->start)
	{
	intervals.insert(it, newInterval);
	return intervals;
	}
	else if(newInterval.start>it->end)
	{
	it++;
	continue;
	}
	else
	{
	newInterval.start=std::min(newInterval.start, it->start);
	newInterval.end=std::max(newInterval.end, it->end);
	it=intervals.erase(it);
	}
	}
	intervals.insert(intervals.end(), newInterval);
	return intervals;
	}
	vector<Interval> merge(vector<Interval> &intervals) {
	// Start typing your C/C++ solution below
	// DO NOT write int main() function
	vector<Interval> res;
	vector<Interval>::iterator it=intervals.begin();
	while(it!=intervals.end())
	{
	insert(res,*it);
	it++;
	}
	return res;
	}
	};

view raw merge intervals hosted with ❤ by GitHub