P200 区间插入

描述#

这个题目说的是，给你一个没有重叠的区间序列，每个区间用一个开始下标和一个结束下标来表示，并且给你的区间序列已经按开始下标从小到大排序。现在给你一个新区间，你要把它插入到这个区间序列，使得区间序列保持有序并且不重叠， 必要时可以进行区间合并。

比如说，给你的区间序列是：
[1,2], [3,4], [5,7], [8,9]
要插入的区间为：
[4,6]
区间 [4,6] 和区间 [3,4]、[5,7] 有重叠。这三个重叠的区间合并后，得到区间：
[3,7]
因此，插入新区间后，得到的区间序列是：
[1,2], [3,7], [8,9]

相关视频：区间合并

代码#

public class AlgoCasts {

  // Time: O(n), Space: O(n)
  public int[][] insertByMerge(int[][] intervals, int[] newInterval) {
    int[][] tmp = new int[intervals.length+1][2];
    int size = 0, p = 0;

    for (; p < intervals.length && intervals[p][0] < newInterval[0]; ++p)
      tmp[size++] = intervals[p];

    if (size == 0 || tmp[size-1][1] < newInterval[0]) {
      tmp[size++] = newInterval;
    } else {
      tmp[size-1][1] = Math.max(tmp[size-1][1], newInterval[1]);
    }

    for (; p < intervals.length; ++p) {
      if (tmp[size-1][1] < intervals[p][0]) {
        tmp[size++] = intervals[p];
      } else {
        tmp[size-1][1] = Math.max(tmp[size-1][1], intervals[p][1]);
      }
    }
    return Arrays.copyOf(tmp, size);
  }

  // Time: O(n), Space: O(n)
  public int[][] insertExpandNewInterval(int[][] intervals, int[] newInterval) {
    int[][] tmp = new int[intervals.length+1][2];
    int size = 0, p = 0;

    for (; p < intervals.length && intervals[p][1] < newInterval[0]; ++p)
      tmp[size++] = intervals[p];

    for (; p < intervals.length && intervals[p][0] <= newInterval[1]; ++p) {
      newInterval[0] = Math.min(newInterval[0], intervals[p][0]);
      newInterval[1] = Math.max(newInterval[1], intervals[p][1]);
    }
    tmp[size++] = newInterval;

    for (; p < intervals.length; ++p)
      tmp[size++] = intervals[p];

    return Arrays.copyOf(tmp, size);
  }

}