[LeetCode]Merge Interval

题目链接

按照start从小到大sort一遍，我们维护一个已经merge了的intervals的集合merged。对于每一个interval，如果其start大于merged尾部interval的end，我们就把interval push到merged中。否则，说明和merged中最后一个interval相交，我们看情况更新merged尾部interval的end。时间复杂度O(n * log n)，代码如下：

	/**
	* 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> merge(vector<Interval>& intervals) {
	int len = intervals.size();
	auto comp = [](const Interval& lhs, const Interval& rhs){return lhs.start < rhs.start;};
	sort(intervals.begin(), intervals.end(), comp);
	vector<Interval> res;
	for(int i = 0; i < len; ++i)
	{
	auto interval = intervals[i];
	if(res.empty())res.push_back(interval);
	else
	{
	auto last = res.back();
	if(interval.start > last.end)res.push_back(interval);
	else res.back().end = max(last.end, interval.end);
	}
	}
	return res;
	}
	};

view raw Merge Intervals.cpp hosted with ❤ by GitHub