给出一个区间的集合，请合并所有重叠的区间。
示例 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] 可被视为重叠区间。
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/merge-intervals 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路:先排序，然后判断后一个是否与前一个可以合并，可以就更新右端点;也可以使用一个标记，然后从当前位置开始遍历往下的位置，判断区间是否重合，标记左端点和右端点
template <typename T
>
struct Compare
{
public:
bool operator() (vector
<T
> v1
,vector
<T
> v2
) const{
return v1
[0] == v2
[0] ? (v1
[1] < v2
[1]) : (v1
[0] < v2
[0]);
}
};
class Solution {
public:
vector
<vector
<int>> merge1(vector
<vector
<int>>& intervals
) {
vector
<vector
<int>> ret
;
if(intervals
.size() == 0)
return ret
;
std
::sort(intervals
.begin(),intervals
.end(),Compare
<int>());
ret
.push_back(intervals
[0]);
int n
= 0;
for(int i
=1;i
<intervals
.size();i
++){
if(intervals
[i
][0] <= ret
[n
][1]){
ret
[n
][1] = max(ret
[n
][1],intervals
[i
][1]);
}else{
ret
.push_back(intervals
[i
]);
n
++;
}
}
return ret
;
}
vector
<vector
<int>> merge(vector
<vector
<int>>& intervals
) {
vector
<vector
<int>> ret
;
if(intervals
.size() == 0)
return ret
;
std
::sort(intervals
.begin(),intervals
.end(),Compare
<int>());
for(int i
=0;i
<intervals
.size();i
++){
int a
= intervals
[i
][0];
int b
= intervals
[i
][1];
int j
= i
+ 1;
while(j
< intervals
.size() && intervals
[j
][0] <= b
){
b
= max(b
,intervals
[j
][1]);
j
++;
}
ret
.push_back(vector
<int>{a
,b
});
i
= j
- 1;
}
return ret
;
}
};
