博文中会简要介绍Leetcode P0057题目分析及解题思路。
“Insert Interval”是p0056的变形题，基本思路一致。
Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).
You may assume that the intervals were initially sorted according to their start times.
Example 1:
Input: intervals = [[1,3],[6,9]], newInterval = [2,5] Output: [[1,5],[6,9]]
由于题目明确指出，初始的时间间隔数组已经按照起始时间排好序了，所以就不用再额外排序。具体的边界条件详见Java代码注释，这里不再赘述。
以下是Java的题解代码实现。
class Solution {
public int[][] insert(int[][] intervals, int[] newInterval) {
if (intervals == null || intervals.length == 0)
return new int[][] {newInterval};
List<int[]> merged = new ArrayList<>();
for (int[] interval: intervals) {
// 左端有重叠
if (newInterval[0] >= interval[0] && newInterval[0] <= interval[1]) {
newInterval[0] = Math.min(interval[0], newInterval[0]);
newInterval[1] = Math.max(interval[1], newInterval[1]);
}
// 右端有重叠
else if (newInterval[1] >= interval[0] && newInterval[1] <= interval[1]) {
newInterval[0] = Math.min(interval[0], newInterval[0]);
newInterval[1] = Math.max(interval[1], newInterval[1]);
}
// 整体覆盖
else if (newInterval[0] < interval[0] && newInterval[1] > interval[1]) {
continue;
}
// 两端无重叠，且整体也不覆盖
else {
if (interval[1] < newInterval[0])
merged.add(interval);
else if (interval[0] > newInterval[1]) {
merged.add(newInterval);
// 更新newInterval为当前interval，由于没有重叠所以后续每次条件判断都会落入“两端无重叠，且整体也不覆盖”。
newInterval = interval;
}
}
}
merged.add(newInterval);
// Java 8 stream()方法
// return merged.stream().toArray(int[][]::new);
return merged.toArray(new int[0][0]);
}
}