Given a collection of intervals, merge all overlapping intervals.
For example,
1 2
| Given [1,3],[2,6],[8,10],[15,18], return [1,6],[8,10],[15,18].
|
O(n log n) solution
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37
| * Definition for an interval. * public class Interval { * int start; * int end; * Interval() { start = 0; end = 0; } * Interval(int s, int e) { start = s; end = e; } * } */ public class Solution { public List<Interval> merge(List<Interval> intervals) { if (intervals == null || intervals.size() < 2){ return intervals; } Collections.sort(intervals, new Comparator<Interval>(){ @Override public int compare(Interval i1, Interval i2){ return i1.start - i2.start; } }); List<Interval> result = new LinkedList<Interval>(); Interval prev = null; for (Interval interval : intervals){ if (prev == null || prev.end < interval.start){ result.add(interval); prev = interval; }else{ prev.end = Math.max(prev.end, interval.end); } } return result; } }
|