If we cease to believe in love, why would we want to live? 如果我们不相信爱，那又为何而活呢？ 问题描述 给出一个无重叠的 ，按照区间起始端点排序的区间列表。 在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。 示例 1： 输入： intervals = [[1,3],[6,9]] newInterval = [2,5] 输出：[[1,5],[6,9]] 示例 2： 输入： intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]] newInterval = [4,8] 输出：[[1,2],[3,10],[12,16]] 解释：这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。 先计算两边再计算中间 这里我们人为把数组分为3部分，左边不重合的（如果有）添加到集合list中，右边不重合的（如果有）也添加到集合list中，然后再合并中间的，这里以示例2为例画个图看一下
原理很简单，来看下代码
1public int[][] insert(int[][] intervals, int[] newInterval) {
2 //边界条件判断
3 if (intervals.length == 0)
4 return new int[][]{newInterval};
5 List<int[]> resList = new ArrayList<>();
6
7 //一个从左边开始找不重合的
8 int left = 0;
9 //一个从右边开始找不重合的
10 int right = intervals.length - 1;
11
12 //左边不重合的添加到list中
13 while (left < intervals.length && intervals[left][1] < newInterval[0]) {
14 resList.add(intervals[left++]);
15 }
16
17 //右边不重合的添加到list中
18 while (right >= 0 && intervals[right][0] > newInterval[1]) {
19 resList.add(left, intervals[right--]);
20 }
21
22 //下面一大坨是合并中间重合的，注意一些边界条件的判断
23 int[] newArr = new int[2];
24 newArr[0] = left >= intervals.length ? newInterval[0] : Math.min(intervals[left][0], newInterval[0]);
25 newArr[1] = right < 0 ? newInterval[1] : Math.max(intervals[right][1], newInterval[1]);
26 resList.add(left, newArr);
27
28 //这一大坨是把list转二维数组
29 int[][] resArr = new int[resList.size()][2];
30 for (int i = 0; i < resList.size(); i++) {
31 resArr[i] = resList.get(i);
32 }
33 return resArr;
34}
35
逐步合并
上面一种方式是先把两边不重合的添加到集合list中，之后在合并中间的。这里还可以从左边开始把不重合的（如果有不重合的）添加到集合list中，如果遇到重合的就找出重合的范围然后再添加到集合中，最后再把后面不重合的（如果有）添加到集合list中。
1public int[][] insert(int[][] intervals, int[] newInterval) {
2 List<int[]> resList = new ArrayList<>();
3 int i = 0;
4 //先把前面不重合的添加到list中
5 while (i < intervals.length && intervals[i][1] < newInterval[0])
6 resList.add(intervals[i++]);
7
8 int mergeStar = newInterval[0];
9 int mergeEnd = newInterval[1];
10 //前面不重合的都添加到集合list中了，从这里开始就出现重合了，我们要找到重合的开始和结束值
11 while (i < intervals.length && intervals[i][0] <= newInterval[1]) {
12 mergeStar = Math.min(mergeStar, intervals[i][0]);
13 mergeEnd = Math.max(mergeEnd, intervals[i][1]);
14 i++;
15 }
16 //然后再把重合的添加到list中
17 resList.add(new int[]{mergeStar, mergeEnd});
18
19 //把剩下的在添加到集合list中
20 while (i < intervals.length)
21 resList.add(intervals[i++]);
22
23 //这一大坨是把list转二维数组
24 int[][] resArr = new int[resList.size()][2];
25 for (int j = 0; j < resList.size(); j++) {
26 resArr[j] = resList.get(j);
27 }
28 return resArr;
29}
总结
这题难度不是很大，但一次写出来不出错比较困难，因为他有很多边界条件的判断。
联系客服
