The problem:

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

My analysis:

If you could have a clear idea about each possible conditions, when sort the interval or decide the new interval's start and end boundary, the problem is very easy!1. Inorder to find out ther overlapping intervals by only traversaling the List once, we need to firstly sort the intervals (according to the start of the interval). There could be two cases:1.1 Interval i2's start position is strictly greater than i1.1.2 Interval i2's start position is the same as that of the interval i1, but i2's end position is strictly greater than i1's. Note: the sort in interval is very very important, these two are classic ways. Skill: we need to write a comparator for it.Comparator
     
       comp = new Comparator
      
        () {        @Override        public int compare(Interval i1, Interval i2) {         //if i1 should be ordered before i2, return negative value        if (i1.start == i2.start)                return i1.end - i2.end;            return i1.start - i2.start;        }};2. How to decide whether two intervals are overlapping?Since we scan the intervals list from the sorted order(compare start position), we only need to compare the pre window(interval)'s end position and end window(position)'s start position. we could classify it into two cases:Assume: Interval1 {}     Interval2[]2.1 { [ } ]2.2 { [ ] }from the above analysis, we could know that we could detect overlaypping through "if (pre.end >= cur.start)", and we need to decide the new window's end boundary through following way:if (pre.end >= cur.start) {    pre.end = (pre.end > cur.end ? pre.end : cur.end);}3. The invariant I used in this solution:3.1 iff current interval is overlapping with the pre interval, we includ the current interval into the pre interval, by adjusting the start and end position's value.3.2 iff not, we add the pre interval into the answer set and update the pre interval into the current one. Since we add the pre interval at the next independent interval.To use this invariant, we need: 3.1 set intervals(0) as the pre intervalInterval pre = new Interval(intervals.get(0).start, intervals.get(0).end);3.2 begin the invariant from interval(1)for (int i = 1; i < intervals.size(); i++) {...}3.3 add the last interval outside the for loop.ret.add(pre);
      
     

 

My solution:

public class Solution {    public List
     
       merge(List
      
        intervals) {        ArrayList
       
         ret = new ArrayList
        
          ();        if (intervals == null || intervals.size() == 0)            return ret;                Comparator
         
           comp = new Comparator
          
            () { @Override public int compare(Interval i1, Interval i2) { if (i1.start == i2.start) return i1.end - i2.end; return i1.start - i2.start; } }; Collections.sort(intervals, comp); Interval pre = new Interval(intervals.get(0).start, intervals.get(0).end); for (int i = 1; i < intervals.size(); i++) { Interval cur = intervals.get(i); if (pre.end >= cur.start) { pre.end = (pre.end > cur.end ? pre.end : cur.end); } else { //a separtate interval ret.add(pre); pre = new Interval(cur.start, cur.end); } } ret.add(pre); return ret; }}