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].
把给定数组区间重复部分合并，返回合并后的区间状态。
如果区间按照左端点位置升序排列，可以维护一个左右边界，当新增一个区间A1时，有两种情况：1、A1左端点大于当前右边界，此时不存在交集，则把当前左右边界作为一个Interval加入到结果集中，再把左右边界更新成A1的两端；2、A1左端点小于等于右边界，并且A1右端点大于当前右边界，则右边界更新为A1的右端点。
public List<Interval> merge(List<Interval> intervals) {
List<Interval> res = new ArrayList<>();
if (intervals == null || intervals.size() == 0) {
return res;
}
Collections.sort(intervals, new Comparator<Interval>() {
public int compare(Interval i1, Interval i2) {
return i1.start - i2.start;
}
});
int left = Integer.MIN_VALUE, right = Integer.MIN_VALUE;
for (Interval val : intervals) {
if (val.start > right) {
if (right != Integer.MIN_VALUE) {
res.add(new Interval(left, right));
}
left = val.start;
right = val.end;
} else if (val.end > right) {
right = val.end;
}
}
res.add(new Interval(left, right));
return res;
}