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

 

遍历list，将每个interval插入到result中去

insert interval :  http://www.cnblogs.com/RazerLu/p/3532267.html

 

/** * 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 ArrayList
          
            merge(ArrayList
           
             intervals) {        ArrayList
            
              result = new ArrayList
             
              ();                for(int i =0; i < intervals.size(); i++){            Interval temp = intervals.get(i);            result = insert(result, temp);        }         return result;    }        public ArrayList
              
                insert(ArrayList
               
                 intervals, Interval newInterval) { ArrayList
                
                  result = new ArrayList
                 
                  (); for(int i = 0; i < intervals.size(); i ++){ Interval temp = intervals.get(i); if(temp.start> newInterval.end){ result.add(newInterval); for(int j = i; j < intervals.size(); j++){ result.add(intervals.get(j)); } return result; } else if( newInterval.start > temp.end){ result.add(temp); continue; } else{ // Attention : method Math.min and Math.max newInterval.start = Math.min(newInterval.start, temp.start); newInterval.end = Math.max(newInterval.end, temp.end); } } /*easy to forget. The situation that newInterval.start is the biggest */ result.add(newInterval); return result; }}