继续打卡算法题，今天学习的是LeetCode第57题插入区间，这道题目是道中等题。算法题的一些解题思路和技巧真的非常巧妙，每天看一看算法题和解题思路，我相信对我们的编码思维和编码能力有一些提升。
分析一波题目
上一题56题合并区间 已经学习了怎么判断重叠区间，怎么合并区间，本题就不难了。最简单的做法，我们可以把要插入的区间和原区间集合先添加到一个新的区间集合，然后排序，最后做一次合并，后面的流程和56题一样。
int[][] newIntervals = new int[intervals.length+1][1];
System.arraycopy(intervals, 0, newIntervals, 0, intervals.length);
newIntervals[newIntervals.length-1] = newInterval;
Arrays.sort(newIntervals, (o1, o2) -> Integer.compare(o1[0], o2[0]));
通过上面的代码组成了新的区间集合，只要对newIntervals中重叠的区间进行合并，这个做法虽好理解，但是性能就降低了，因为题目已经说明原区间已经按左边界排序了,因此本题可以有更优的做法。
由于原区间集已经有序了，我们可以按如下步骤来执行插入操作。
1、将与要插入的区间无重叠的，加入到新的区间集
2、将与要插入的区间有重叠的，执行合并
3、将与要插入的区间无重叠的，加入到新的区间集
本题解题技巧
1、将原区间集分段，分为与新区间左边界偏离的一段，与新区间有重叠的，与新区间右边界偏离的一段
编码解决
重组区间集合，再排序解法
class Solution {
public int[][] insert(int[][] intervals, int[] newInterval) {
//存储结果
LinkedList<int[]> result = new LinkedList<>();
//按左边界排序
int[][] newIntervals = new int[intervals.length+1][1];
//重组新区间集
System.arraycopy(intervals, 0, newIntervals, 0, intervals.length);
newIntervals[newIntervals.length-1] = newInterval;
Arrays.sort(newIntervals, (o1, o2) -> Integer.compare(o1[0], o2[0]));
System.out.println(newIntervals.length);
//第一个先加入结果
result.add(newIntervals[0]);
//从第二个开始判断是否重叠
for (int i = 1; i < newIntervals.length; i++) {
//和前面的重叠了
System.out.println(i);
System.out.println(newIntervals[i]);
if (newIntervals[i][0] <= result.getLast()[1]) {
int start = result.getLast()[0];
int end = Math.max(newIntervals[i][1], result.getLast()[1]);
//合并之前，最后一个需要删除
result.removeLast();
//合并成新区间，并加入结果
result.add(new int[]{
start, end});
}
else {
//没有重叠，加入结果
result.add(newIntervals[i]);
}
}
return result.toArray(new int[result.size()][]);
}
}
不重组区间集且不重新排序解法
class Solution {
public int[][] insert(int[][] intervals, int[] newInterval) {
//存储结果
int[][] result = new int[intervals.length + 1][2];
int idx = 0;
// 1、首先将新区间左边且相离的区间加入结果集
int i = 0;
while (i < intervals.length && intervals[i][1] < newInterval[0]) {
result[idx++] = intervals[i++];
}
// 2、接着判断当前区间是否与新区间重叠，重叠的话就进行合并
while (i < intervals.length && intervals[i][0] <= newInterval[1]) {
newInterval[0] = Math.min(intervals[i][0], newInterval[0]);
newInterval[1] = Math.max(intervals[i][1], newInterval[1]);
i++;
}
//合并的结果存入
result[idx++] = newInterval;
// 3、最后将新区间右边且相离的区间加入结果集
while (i < intervals.length) {
result[idx++] = intervals[i++];
}
return Arrays.copyOf(result, idx);
}
}
总结
1、通过借助56题合并区间思路，可以解决本题，合并区间和判断区间重叠的方法同样适用
2、借助原区间集本身有序的特性，通过拆分3步，根据新区间和原区间集的关系，要么有交集，要么在区间集左边，执行插入操作，并且时间复杂度控制在O(n)。
