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].
Analysis
We can sort the intervals first. They are sorted by their “start” value. If the “start” value is the same, “end” value is used to compare them. In Java, it’s very easy to sort them by writing a comparator.
Code
|
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 38 39 |
public class Solution { public List<Interval> merge(List<Interval> intervals) { List<Interval> ret = new LinkedList<>(); if (intervals.size() == 0) return ret; Collections.sort(intervals, new Comparator<Interval>() { @Override public int compare(Interval o1, Interval o2) { if (o1.start > o2.start) return 1; else if (o1.start < o2.start) return -1; else { if (o1.end > o2.end) return 1; else if (o1.end < o2.end) return -1; } return 0; } }); Interval t = null; for (Interval interval : intervals) { if (t == null) t = interval; else { if (t.end >= interval.start) { t.end = Math.max(t.end, interval.end); } else { ret.add(t); t = interval; } } } ret.add(t); return ret; } } |
Complexity
Sorting costs $O(nlogn)$. And merging the sorted intervals costs $O(n)$. So the complexity is $O(nlogn)$.