https://leetcode.cn/problems/merge-intervals/

排序再合并

  • 先按每个区间的左端点排一下序
  • 然后遍历
    • 看当前左端点是否大于上一个区间的右端点
      • 若是，则把上一个区间生成然后加入结果列表中， 重置左右端点为自己的左右端点
      • 若不大于，则看当前右端点是否能把上一个区间的右端点推高，若能，更新一下
    • 由于每次生成时机都是生成上一个的，所以在循环轮到最后一个的时候没生成，所以要在外边最后一个
  1.  public int[][] merge(int[][] intervals) {
  2.      if (intervals == null) return null;
  3.      List<int[]> merge = new ArrayList<>();
  4.      Arrays.sort(intervals, (int[] o1, int[] o2) -> {
  5.          return o1[0] - o2[0];
  6.      });
  7.      int L = intervals[0][0];
  8.      int R = intervals[0][1];
  9.      for (int i = 1; i < intervals.length; i++) {
  10.          if (intervals[i][0] > R) {
  11.              merge.add(new int[]{L, R});
  12.              L = intervals[i][0];
  13.              R = intervals[i][1];
  14.          } else {
  15.              R = Math.max(R, intervals[i][1]);
  16.          }
  17.      }
  18.      merge.add(new int[]{L, R});
  19.      return merge.toArray(new int[merge.size()][2]);
  20.  }