LeeCode: Merge Intervals

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

Solution:
Caution should be exercised when using customized sort function.

The Key Point: two ways to implement user-defined comparator. Similar rule applies to Collections.sort() and Arrays.sort()

For exampe:

 import java.util.*;

public class Test {

    public static void main(String args[]) {

        int[][] twoDim = { {1, 2}, {3, 7}, {8, 9}, {4, 2}, {5, 3} };

        Arrays.sort(twoDim, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return ((Integer) o2[0]).compareTo(o1[0]);
            }
        });

        System.out.println(Arrays.deepToString(twoDim));
    }
}

Reference: int compare(T ol, T or)
Compares its two arguments for order. Returns a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second.


My Solution:

public ArrayList merge(ArrayList intervals) {
        
    if(intervals==null) return intervals;
        
    Collections.sort(intervals, new IntervalComparator());
        
    for(int i=0; i< intervals.size()-1; ){
            
        Interval a = intervals.get(i);
        Interval b = intervals.get(i+1);
            
        if(a.end >= b.start){
            int newEnd = a.end<=b.end? b.end : a.end;
            Interval newIntv = new Interval(a.start, newEnd);
            intervals.remove(i);//removeRange(i, i+1) also works
            intervals.remove(i);//!!!!!intervals.remove(i+1);
            intervals.add(i, newIntv);
        }
        else//no overlap
            i++;
    }
        
    return intervals;
}


class IntervalComparator implements Comparator{
    @Override
    public int compare(Interval a, Interval b){
        if(a.start<b.start)
            return -1;
        if(a.start == b.start&&a.end<b.end)
            return -1;
            
        if(a.start == b.start&&a.end==b.end)
            return 0;
            
        return 1;
    }
    
} 

The Second way to create a new Comparator object by overriding

int compare(....)! Nice~~~~~

 Collections.sort(intervals, new Comparator<Interval>(){
        public int compare(Interval int1, Interval int2) {
            if (int1.start < int2.start) {
                return -1;
            }
            if (int1.start == int2.start && int1.end <= int2.end) {
                return -1;
            }
            return 1;
        }
    });