Merge Intervals
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]
.
分析
- sort by ascending starting point
if start2 is not bigger than end1, which means there is overlapping between two intervals, then we merge these two and update new end for this new merged interval
otherwise, if start3 is bigger than end2, which means there is no overlapping between two intervals, then we directly add this latter interval into result
图解
代码
class Solution {
public List<Interval> merge(List<Interval> intervals) {
// special case
if (intervals.size() <= 1)return intervals;
// Sort by ascending starting point
intervals.sort((o1,o2)->o1.start - o2.start);
List<Interval> result = new LinkedList<Interval>();
int start = intervals.get(0).start;
int end = intervals.get(0).end;
for (Interval interval : intervals) {
if (interval.start <= end) // Overlapping intervals, move the end if needed
end = Math.max(end, interval.end);
else { // Disjoint intervals, add the previous one and reset bounds
result.add(new Interval(start, end));
start = interval.start;
end = interval.end;
}
}
// Add the last interval
result.add(new Interval(start, end));
return result;
}
}