[LeetCode] Merge Intervals

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].

Solution: First sort, then merge.
See also: [LeetCode] Insert Interval.

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 40 41 42 43 44 45 46

/** * 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 { class IntervalComparator implements Comparator<Interval> { public int compare(Interval a, Interval b) { return a.start - b.start; } } private Interval merge(Interval a, Interval b) { int start = Math.min(a.start, b.start); int end = Math.max(a.end, b.end); return new Interval(start, end); } private boolean overlap(Interval a, Interval b) { if (a.end < b.start || b.end < a.start) { return false; } return true; } public List<Interval> merge(List<Interval> intervals) { Collections.sort(intervals, new IntervalComparator()); int i = 0; while (i < intervals.size()) { Interval interval = intervals.get(i); while ( i < intervals.size() && overlap(interval, intervals.get(i)) ) { interval = merge(interval, intervals.remove(i)); } intervals.add(i, interval); i++; } return intervals; } }