56. Merge Intervals

题目

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

解析

分析：题目要求对区间进行合并，首先必须对区间按照左边元素的大小进行排序，然后对排序后的数组进行遍历，合并。能够合并的区间必须符合 a.begin <=b.begin <= a.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:

	static int compare(Interval val1,Interval val2)
	{
		return val1.start < val2.start;
	}

	vector<Interval> merge(vector<Interval>& intervals) {

		if (intervals.size()<=1)
		{
			return intervals;
		}
		sort(intervals.begin(),intervals.end(),compare); //按第一关键字排序
		vector<Interval> vec;
		Interval temp=intervals[0];
		
		for (int i = 1; i < intervals.size(); i++)
		{
			Interval node = intervals[i]; //取出每一个节点
			if (node.start<=temp.end)
			{
				temp.end = max(temp.end,node.end);  // [[1,4],[2,3]]
			}
			else
			{
				vec.push_back(temp);
				temp = intervals[i];
			}
		}
		vec.push_back(temp);
		return vec;
	}
};

题目来源

56. Merge Intervals