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].
题意：合并区间，将给的区间合并成最终版本就可以。
思路：按照区间左侧从小到大排序，如果左侧相同，按照右侧从小到大排序。从左向右，两两合并即可。
public static List<Interval> merge(List<Interval> intervals) {
List<Interval> result = new ArrayList<Interval>();
if (intervals == null || intervals.size() == 0) {
return result;
}
Collections.sort(intervals, new Comparator<Interval>() {
@Override
public int compare(Interval i1, Interval i2) {
if (i1.start != i2.start) {
return i1.start - i2.start;
} else {
return i1.end - i2.end;
}
}
});
Interval pre = intervals.get(0);
for (int i = 0; i < intervals.size(); i++) {
Interval curr = intervals.get(i);
if (curr.start > pre.end) {
result.add(pre);
pre = curr;
} else {
Interval meraged = new Interval(pre.start, Math.max(pre.end, curr.end));
pre = meraged;
}
}
return result;
}
