56. 合并区间
给出一个区间的集合，请合并所有重叠的区间。
示例 1:
输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2:
输入: [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。
思路：
先看一下两个区间怎么合并，[8,10]和[15,18]，先假设第一个区间[8,10]已经是合并好了的，第二个区间[15,18]要与它合并。那么我们只需比较第二个区间的左端点15，和第一个区间右端点10。第二个区间的左端点15大于第一个区间右端点10，说明两个区间是独立的，第一个区间的最大无法包含第二个区间的最小。
再看另一种情况，[1,3]与[2,6]，先假设第一个区间[1,3]已经是合并好了的，第二个区间[2,6]要与它合并。那么我们只需比较第二个区间的左端点2，和第一个区间右端点3。第二个区间的左端点2小于第一个区间右端点3，说明两个区间可以合并，此时要确定的是新区间的左端点和右端点，右端点必然是在第一个区间的右端点和第二个区间的右端点之中的最大值。左端点则是第一个区间的左端点和第二个区间的左端点之中的最小值。要比较确定两次，故可以先将区间向量按每个区间的左端点排序即可。
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
if(intervals.size()==0||intervals[0].size()==0)
return {};
sort(intervals.begin(),intervals.end()); //左端点排序，左端点一样按右端点排
vector<vector<int>> merged;
for(int i=0;i<intervals.size();++i)
{
int L=intervals[i][0],R=intervals[i][1]; //待合并区间的左端点和右端点
if(merged.empty()||merged.back()[1]<L) //待合并区间左端点大于已合并区间右端点
merged.push_back({L,R});
else
merged.back()[1]=max(merged.back()[1],R); //待合并区间左端点小于等于已合并区间右端点
}
return merged;
}
};
