给出一个无重叠的 ，按照区间起始端点排序的区间列表。
在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。
示例 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] 重叠。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/insert-interval
时间复杂度：O（n）
空间复杂度：O（1）
class Solution { public int[][] insert(int[][] intervals, int[] newInterval) { int left = newInterval[0]; int right = newInterval[1]; List<int []> resultList = new ArrayList<int []>(); boolean addNewValue = false; for(int [] layer : intervals){ //说明该层最大的值还要小于left值 if(layer[1] < left){ resultList.add(layer); } else if(layer[0] > right){ //若是该层的最小值大于right //那么首先要把left和right放入到list中 if(!addNewValue){ resultList.add(new int[]{left,right}); addNewValue = true; } //再把当前层放入list resultList.add(layer); } else { //比较left，right得到本层的最大值，最小值，再继续跟下一层对比 left = Math.min(layer[0],left); right = Math.max(layer[1],right); } } //如果还没有把left和right放入到list中 if(!addNewValue){ resultList.add(new int[]{left,right}); } int result[][] = new int [resultList.size()][2]; for(int i = 0 ; i < resultList.size() ; i++){ result[i][0] = resultList.get(i)[0]; result[i][1] = resultList.get(i)[1]; } return result; } }
原文：https://www.cnblogs.com/fengtingxin/p/13929128.html