题目

image.png

思路

  • 以左边起点排序后，只要逐个比较右边大小即可

    代码

    1.   public int[][] merge(int[][] intervals) {
    2.        if (intervals.length == 0) {
    3.           return new int[0][2];
    4.       }
    5.       Arrays.sort(intervals, new Comparator<int[]>() {
    6.           public int compare(int[] interval1, int[] interval2) {
    7.               return interval1[0] - interval2[0];
    8.           }
    9.       });
    10.       List<int[]> merged = new ArrayList<int[]>();
    11.       for (int i = 0; i < intervals.length; ++i) {
    12.           int L = intervals[i][0], R = intervals[i][1];
    13.           if (merged.size() == 0 || merged.get(merged.size() - 1)[1] < L) {
    14.               merged.add(new int[]{L, R});
    15.           } else {
    16.               merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], R);
    17.           }
    18.       }
    19.       return merged.toArray(new int[merged.size()][]);
    20.   }
    22.   //自己实现排序
    23.   public int[][] merge(int[][] intervals) {
    24.       int len = intervals.length;
    25.       if (len <= 1) return intervals;
    26.       for (int i = 1; i < len; i++) {
    27.           int j = i - 1;
    28.           int[] val = intervals[i] ;
    29.           while (j >= 0 && intervals[j][0] > val[0]) {
    30.               intervals[j + 1] = intervals[j];
    31.               j--;
    32.           }
    33.           intervals[j + 1] = val;
    34.       }
    35.       List<int[]> res = new ArrayList<>();
    36.       for (int i = 1; i < len; i++) {
    37.           if (intervals[i - 1][1] >= intervals[i][0]) {
    38.               intervals[i][0] = intervals[i - 1][0];
    39.               if (intervals[i- 1][1] > intervals[i][1])
    40.                    intervals[i][1] = intervals[i - 1][1];
    41.           } else {
    42.               res.add(intervals[i - 1]);
    43.           }
    44.           if (i == len - 1) res.add(intervals[i]);
    45.       }
    46.       return res.toArray(new int[0][0]);
    47.   }

    合并区间