leetcode 56合并区间

思路

合并就是首先应该按照left左边界排序，排完序以后，如果i的左边界小于等于i-1的右边界，说明有重合，此时这两个可以合并，右边界应该取最大值。

代码

排序

我是定义了一个类,存储左右边界，先将数组转化为这个Interval数组，因为我不会二维数组排序

class Interval{
        int left;
        int right;
    }

排序：

 Arrays.sort(intervalss, new Comparator<Interval>() {
            @Override
            public int compare(Interval o1, Interval o2) {
                if (o1.left == o2.left){
                    return o1.right -o2.right;
                }
                return o1.left - o2.left;
            }
        });

后来学习了二维数组排序

Arrays.sort(intervals, new Comparator<int[]>() {
   public int compare(int[] interval1, int[] interval2) {
       return interval1[0] - interval2[0];
   }
});

进行区间合并

  		int min_left = intervalss[0].left;  //每一次合并的左边界
        int max_right = intervalss[0].right;//每一次合并的右边界
        for (int i = 1; i < intervalss.length ; i++) {
            if (intervalss[i].left> max_right ){ //新的最左边的值大于之前的最右边的值，说明连不起来，后面的需要作为一个新的区间,还有就是最后一个，应该直接作为一个新的区间
                List<Integer> list = new ArrayList<>(2);
                list.add(min_left);
                list.add(max_right);
                list2D.add(list);
                min_left = intervalss[i].left;
                max_right = intervalss[i].right;
            }else {
                max_right =Math.max(max_right, intervalss[i].right);
            }
        }
        List<Integer> list = new ArrayList<>(2); //不要忘了对最后一次合并处理，放入结果里面
        list.add(min_left);
        list.add(max_right);
        list2D.add(list);

全部代码：

public  int[][] merge(int[][] intervals) {

        List<List<Integer>> list2D = new ArrayList<>();
        Interval[] intervalss = new Interval[intervals.length];
        for (int i = 0; i < intervals.length; i++) {
            intervalss[i] = new Interval();
            intervalss[i].left = intervals[i][0];
            intervalss[i].right = intervals[i][1];
        }
        Arrays.sort(intervalss, new Comparator<Interval>() {
            @Override
            public int compare(Interval o1, Interval o2) {
                if (o1.left == o2.left){
                    return o1.right -o2.right;
                }
                return o1.left - o2.left;
            }
        });
        Arrays.stream(intervalss).forEach(a -> System.out.println(a.left + " " + a.right));
        int min_left = intervalss[0].left;
        int max_right = intervalss[0].right;
        for (int i = 1; i < intervalss.length ; i++) {
            if (intervalss[i].left> max_right ){ //新的最左边的值大于之前的最右边的值，说明连不起来，后面的需要作为一个新的区间,还有就是最后一个，应该直接作为一个新的区间
                List<Integer> list = new ArrayList<>(2);
                list.add(min_left);
                list.add(max_right);
                list2D.add(list);
                min_left = intervalss[i].left;
                max_right = intervalss[i].right;
            }else {
                max_right =Math.max(max_right, intervalss[i].right);
            }
        }
        List<Integer> list = new ArrayList<>(2); //不要忘了对最后一次合并处理，放入结果里面
        list.add(min_left);
        list.add(max_right);
        list2D.add(list);
        int[][] result = new int[list2D.size()][];
        for (int i = 0;i< list2D.size();i++){
            result[i] = new int[]{list2D.get(i).get(0), list2D.get(i).get(1)};

        }
        return result;
    }
    class Interval{
        int left;
        int right;
    }