给出若干闭合区间,合并所有重叠的部分。
给出若干闭合区间,合并所有重叠的部分。
[ [
[1, 3], [1, 6],
[2, 6], => [8, 10],
[8, 10], [15, 18]
[15, 18] ]
]
题目没有说是有序的集合,所以我们要进行先根据左端点进行排序,排序后,判断右端点与下一个节点的左端点的大小来决定是否合并区间。
/**
* Definition of Interval:
* public class Interval {
* int start, end;
* Interval(int start, int end) {
* this.start = start;
* this.end = end;
* }
*/
class Solution {
/**
* @param intervals, a collection of intervals
* @return: A new sorted interval list.
*/
public List<Interval> merge(List<Interval> intervals) {
List<Interval> ans = new ArrayList<Interval>();
Collections.sort(intervals, new Comparator<Interval>(){
@Override
public int compare(Interval obj1, Interval obj2){
return obj1.start - obj2.start;
}
});
Interval last = null;
for (Interval item : intervals) {
if (last == null || last.end < item.start) {
ans.add(item);
last = item;
} else {
last.end = Math.max(last.end, item.end);
}
}
return ans;
}
}