Merge Intervals

 1 public class Solution {
 2     public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
 3         // IMPORTANT: Please reset any member data you declared, as
 4         // the same Solution instance will be reused for each test case.
 5         ArrayList<Interval> result = new ArrayList<Interval>();
 6         if(intervals == null || intervals.size() == 0)
 7             return result;
 8             
 9         Comparator<Interval> comparator = new Comparator<Interval>() {
10             public int compare(Interval i1, Interval i2) {
11                 if (i1.start < i2.start)
12                     return -1;
13                 else if (i1.start > i2.start)
14                     return 1;
15                 else {
16                     if (i1.end < i2.end)
17                         return -1;
18                     else if (i1.end > i2.end)
19                         return 1;
20                     else
21                         return 0;
22                 }
23             }
24         };
25     Collections.sort(intervals, comparator);
26         Interval newinterval = new Interval(intervals.get(0).start, intervals.get(0).end);
27         
28         for(int i = 1; i < intervals.size(); i++){
29             Interval tmp = intervals.get(i);
30             if(newinterval.end < tmp.start){
31                 result.add(newinterval);
32                 newinterval = new Interval(tmp.start, tmp.end);
33             }
34             else{
35                 newinterval.end = Math.max(newinterval.end, tmp.end);
36             }
37         }
38         result.add(newinterval);
39         return result;
40     }
41     
42 }