leetcode 56 Merge Intervals ----- java

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

这道题就是合并所有集合，虽然是hard难度，但是还是比较好想出来的，就是重写compare，然后对所有集合进行排序，排序之后再进行比较久ok了。

［A,B］与［C,D］

在已经排序的前提下，比较B与C的大小，如果B大，那么合并两个集合，取出D与下一个集合进行比较

　　　　　　　　　　　　　　　　　　如果C大，那么直接添加集合进result。

最后再进行一次判断（最后一个集合是否加入了result中）。

但是第一次提交compare定义出现了错误。

/**
 * 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 List<Interval> merge(List<Interval> intervals) {
        List<Interval> result = new ArrayList<Interval>();
        int len = intervals.size();
        if( len < 2 )
            return intervals;
        Comparator<Interval> comparator = new Comparator<Interval>(){
            public int compare(Interval i1,Interval i2){
                if( i1.start>i2.start)
                    return 1;
                else 
                    return -1;
            }
        };
        Collections.sort(intervals, comparator);
        int[] start = new int[len];
        int[] end = new int[len];
        for( int i = 0;i<len;i++){
            start[i] = intervals.get(i).start;
            end[i] = intervals.get(i).end;
        }
        int begin,over;
        int i = 0,j = 1;
        while( i< len ){
            if( i == len-1){
                result.add(intervals.get(i));
                return result;
            }
            Interval ans = new Interval();
            ans.start = start[i];
            begin = start[j];
            over = end[i];
            while( over >= begin ){
                over = over>end[j]?over:end[j];
                j++;
                if( j == len)
                    break;
                begin = start[j];
            }
            ans.end = over;
            result.add(ans);
            
            i = j;
            j = j+1;
        }
        
        
        return result;
    }
}

然后发现并不是超时，只是对于compare重写的时候出现了问题。

jdk  1.7以前compare只能返回1与－1，但是1.7以后当两个数相同需要返回0，因为compare(a,b)与compare(b,a)要返回相反的数，所以这里出现了问题，然后稍微修改一下，并且做了一些细微的调整，结果还算满意。

/**
 * 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 List<Interval> merge(List<Interval> intervals) {
        List<Interval> result = new ArrayList<Interval>();
        int len = intervals.size();
        if( len < 2 )
            return intervals;
        Comparator<Interval> comparator = new Comparator<Interval>(){
            public int compare(Interval i1,Interval i2){
                if( i1.start>i2.start)
                    return 1;
                else if( i1.start == i2.start)
                    return 0;
                else
                    return -1;
            }
        };
        Collections.sort(intervals, comparator);
        int begin,over;
        int i = 0,j = 1,k = 0;
        while( i< len && j < len){
            Interval ans = new Interval();
            ans.start = intervals.get(i).start;
            begin = intervals.get(j).start;
            over = intervals.get(i).end;
            while( over >= begin ){
                over = over>intervals.get(j).end?over:intervals.get(j).end;
                j++;
                if( j == len)
                    break;
                begin = intervals.get(j).start;
            }
            ans.end = over;
            result.add(ans);
            i = j;
            j = j+1;
            k++;
        }
        if( result.get(k-1).end < intervals.get(len-1).start )
            result.add(intervals.get(len-1));
        
        return result;
    }
}

 然后发现别人的答案中，有一个很难发现的细节，就是如果将start和end分别放入两个数组中，再进行排序，最后的结果与直接将intervals排序得到的结果一样，而这样做的话，就直接达到了最快。其实想法是一样的，还是以前说的，算法是一方面，另一个方面就是存储方式。两者都很关键。

/**
 * 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 List<Interval> merge(List<Interval> intervals) {
        List<Interval> result = new ArrayList<Interval>();
        int len = intervals.size();
        if( len < 2 )
            return intervals;
        int[] start = new int[len];
        int[] end = new int[len];
        for( int i = 0;i<len;i++){
            start[i] = intervals.get(i).start;
            end[i] = intervals.get(i).end;
        }
        Arrays.sort(start);
        Arrays.sort(end);
        int begin,over;
        int i = 0,j = 1;
        while( i< len ){
            if( i == len-1){
                result.add(new Interval(start[i],end[i]));
                return result;
            }
            Interval ans = new Interval();
            ans.start = start[i];
            begin = start[j];
            over = end[i];
            while( over >= begin ){
                over = over>end[j]?over:end[j];
                j++;
                if( j == len)
                    break;
                begin = start[j];
            }
            ans.end = over;
            result.add(ans);
            
            i = j;
            j = j+1;
        }
        
        
        return result;
    }
}