Given a collection of intervals, merge all overlapping intervals.
For example,
Given
return
Given
[1,3],[2,6],[8,10],[15,18]
,return
[1,6],[8,10],[15,18]
.
Solution:O(n logn)
public class Solution {
public ArrayList merge(ArrayList intervals) {
if (intervals == null || intervals.size() <= 1)
return intervals;
Collections.sort(intervals, new IntervalComparator());
ArrayList result = new ArrayList();
Interval prev = intervals.get(0);
for (int i = 1; i < intervals.size(); i++) {
Interval curr = intervals.get(i);
if (prev.end >= curr.start) { Interval merged = new Interval(prev.start, Math.max(prev.end, curr.end)); prev = merged; } else { result.add(prev); prev = curr; } } result.add(prev); return result;
} } class IntervalComparator implements Comparator { public int compare(Interval i1, Interval i2) { return i1.start - i2.start; } }
沒有留言:
張貼留言