56. 合并区间

image.png

题解

执行耗时:9 ms，击败了23.07% 的Java用户 内存消耗:41.2 MB，击败了23.64% 的Java用户

  1. class Solution {
  2.     public int[][] merge(int[][] intervals) {
  3.         Arrays.sort(intervals, Comparator.comparingInt(o -> o[0]));
  5.         // 用于保存合并的结果
  6.         List<int[]> merged = new ArrayList<>();
  7.         for (int i = 0; i < intervals.length; i++) {
  8.             int L = intervals[i][0], R = intervals[i][1];
  9.             int size = merged.size();
  11.             // 如果merge为空
  12.             // 或者如果merge最后一个元素的右边小于当前数组的左边，说明与上一元素不重叠
  13.             // 直接将当前数组添加到merged
  14.             if (size == 0 || merged.get(size - 1)[1] < L) {
  15.                 merged.add(new int[] {L, R});
  16.             } else {
  17.                 // 否则说明需要合并
  18.                 // 合并的方法是更新merged的最后一个元素的右边
  19.                 // 取当前数组的右边与merged的最后一个元素的右边中的大值
  20.                 merged.get(size - 1)[1] = Math.max(R, merged.get(size - 1)[1]);
  21.             }
  22.         }
  23.         return merged.toArray(new int[merged.size()][2]);
  24.     }
  25. }