[Sort] Merge Interval

1. Example
Change end in-place
Given [1,3][2,6][8,10][15,18]
return [1,6],[8,10],[15,18]

2 .Implementation
Q1: sort ?
A1: sort the intervals int[][2] X, List<Interval>
collection.sort(List, new IntervalComparator() );
public int IntervalComparator(Itnerval intervalA, Interval intervalB) implements comparator
{
       if (intervalA.start - intervalB.start  < 0 )
            return -1;
       else
            return 1;
};
Q1: after sorting , how to do the merge ? Detect Merge?
A1: previous's end is larger than next's start, create a new Interval to merge with start from previous's start and end from next's end. list Add and Remove
Q1: Comparator Interface Class? Comparable class  Interface?
A1: interface using implement keyword, class using extend keyword
Comparator<T> comp = new Comparator<T>()
{
         @Override
         public int compare(T t1, T t2)
        {
                return t1.data - t2.data;
        }
};
Collections.sort(  DS, comparator)??
// NOTE:
if (res.get(res.size()-1).end >= intervals.get(i).start ) 

{ 

//Interval item = new Interval(intervals.get(i).start, intervals.get(i+1).end); 

//res.add(item); 

//i++; 

res.get(res.size()-1).end = Math.max(res.get(res.size()-1).end ,intervals.get(i).end);

 }

/*
 Time:O(nlogn+n), Space:O(1)
 
 
 Input:
[[1,3]]
Output:
[]
Expected:
[[1,3]]
 
 Input:
[[1,4],[5,6]]
Output:
[[1,4]]
Expected:
[[1,4],[5,6]]
 
 
 http://codeganker.blogspot.com/2014/03/merge-intervals-leetcode.html
 */
public class Solution {
    public List merge(List intervals) {
                List res = new ArrayList();        





         // validate the input
         if (intervals == null || intervals.size() == 0 )
             return res;






         // Comparator is a class
         Comparator comp = new Comparator()
         {
             @Override
             public int compare(Interval a, Interval b)
             {
                 // NOTE: start are the same
                 if (a.start == b.start)
                     return a.end - b.end; // means a.end < b.end => return -1
                 return a.start - b.start;        
             }
         };








         
         //Collections.sort(intervals, new IntervalComparator());
         Collections.sort(intervals, comp);








         //for ( int i =0 ; i < intervals.size() -1 ;i++)
         res.add(intervals.get(0));
         for (int i = 1; i < intervals.size(); i++)
         {
                //if ( intervals.get(i).end >= intervals.get(i+1).start )
                if (res.get(res.size()-1).end >= intervals.get(i).start )
                {
                    //Interval item = new Interval(intervals.get(i).start, intervals.get(i+1).end);
                    //res.add(item);
                    //i++;
                    res.get(res.size()-1).end = Math.max(res.get(res.size()-1).end ,intervals.get(i).end);
                }
                else 
                {
                    res.add(intervals.get(i));
                }
         }





        
         return res; 




    }
}

//public int IntervalComparator(Interval a, Interval b) implements //Comparator
//{
//    if (a.start < b.start)
//         return -1;
//    else 
//         return 1;
//}

3. Similar ones
[sort] Sort Color
[sort] Sort List