P60 区间合并

描述#

这个题目说的是，给你一个区间集合，你要把有重叠的区间合并起来。

比如说，给你的区间集合是：
[1, 8]
[2, 4]
[9, 10]
[10, 16]
这 4 个区间里，[1, 8] 区间包含了 [2, 4] 区间，于是它们合并后是 [1, 8]。
[9, 10] 区间和 [10, 16] 区间相邻，合并起来后是 [9, 16]。最后得到合并后的区间有两个：
[1, 8]
[9, 16]

代码#

public class AlgoCasts {

  public class Interval {
    int start;
    int end;
    Interval() { start = 0; end = 0; }
    Interval(int s, int e) { start = s; end = e; }
  }

  // Time: O(n*log(n)), Space: O(1)
  public List<Interval> merge(List<Interval> intervals) {
    List<Interval> result = new ArrayList<>();
    intervals.sort((a, b) -> a.start - b.start);

    for (Interval in: intervals) {
      int n = result.size();
      if (result.isEmpty() || result.get(n-1).end < in.start) {
        result.add(in);
      } else {
        result.get(n-1).end = Math.max(result.get(n-1).end, in.end);
      }
    }
    return result;
  }

  // Just another method signature
  public int[][] merge(int[][] intervals) {
    int[][] result = new int[intervals.length][2];
    int size = 0;
    Arrays.sort(intervals, (a, b) -> a[0] - b[0]);

    for (int[] in: intervals) {
      if (size == 0 || result[size-1][1] < in[0]) {
        result[size][0] = in[0];
        result[size][1] = in[1];
        ++size;
      } else {
        result[size-1][1] = Math.max(result[size-1][1], in[1]);
      }
    }
    return Arrays.copyOf(result, size);
  }

}