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].
public class Solution { public ArrayList<Interval> merge(ArrayList<Interval> intervals) { // Start typing your Java solution below // DO NOT write main() function if(intervals.size() == 0){ return intervals; } Collections.sort(intervals, order); ArrayList<Interval> result = new ArrayList<Interval>(); int s = intervals.get(0).start; int e = intervals.get(0).end; for(int i = 1 ; i < intervals.size(); i++){ Interval temp = intervals.get(i); if(e >= temp.start ){//overlaps e = Math.max(e,temp.end); } else{ result.add(new Interval(s,e)); e = temp.end; s = temp.start; } } //the last set of intervals are not added notice here! result.add(new Interval(s, e)); return result; } static final Comparator<Interval> order = new Comparator<Interval>(){ public int compare(Interval i, Interval j){ return new Integer(i.start).compareTo(new Integer(j.start)); } }; }
public class Solution { public ArrayList<Interval> merge(ArrayList<Interval> intervals) { if (intervals == null || intervals.size() <= 1) return intervals; // sort intervals by using self-defined Comparator Collections.sort(intervals, new IntervalComparator()); ArrayList<Interval> result = new ArrayList<Interval>(); Interval prev = intervals.get(0); for (int i = 1; i < intervals.size(); i++) { Interval curr = intervals.get(i); if (prev.end >= curr.start) { // merged case Interval merged = new Interval(prev.start, Math.max(prev.end, curr.end)); prev = merged; } else { result.add(prev); prev = curr; } } result.add(prev);// do not forget add last one return result; } } class IntervalComparator implements Comparator<Interval> { public int compare(Interval i1, Interval i2) { return i1.start - i2.start; } }
mistakes: prev has to be changed to curr after added new merged list