0056 合并区间.md

0056 合并区间

Question:

给出一个区间的集合，请合并所有重叠的区间。

示例 1:

输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2:

输入: [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

Solution:

class Solution {
    public int[][] merge(int[][] intervals) {
        if(intervals.length==0)
            return intervals;
        Arrays.sort(intervals,new MyComparator());
        LinkedList<int[]> ll=new LinkedList<>();
        ll.add(intervals[0]);
        for(int i=1;i<intervals.length;i++){
            int[] last=ll.getLast();
            int right=last[1];
            if(intervals[i][0]<=right){
                ll.removeLast();
                right=Math.max(right,intervals[i][1]);
                ll.add(new int[]{last[0],right});
            }else{
                ll.add(intervals[i]);
            }
        }
        int[][] merged=new int[ll.size()][2];
        for(int i=0;i<ll.size();i++){
            merged[i]=ll.get(i);
        }
        return merged;
    }
}

class MyComparator implements Comparator<int[]>{
     @Override
     public int compare(int[] i1, int[] i2) {
         if(i1[0] < i2[0]) { 
             return -1;
         }else if(i1[0] > i2[0]) {
             return 1;
         }else {
             return 0;
         }
     }
}