Difficulty: 困难
给出一个_无重叠的 ，_按照区间起始端点排序的区间列表。
在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。
示例 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] 重叠。类似题目： 56. 合并区间
//先将newInterval按照顺序插入intervals中，然后再合并区间 import java.util.ArrayList; import java.util.List; import java.util.Map; class Solution { public int[][] insert(int[][] intervals, int[] newInterval) { int len = intervals.length; if(len <= 0){ int[][] res = new int[1][2]; res[0] = newInterval; return res; } List<int[]> list = new ArrayList<>(); intervals = insertIntervals(intervals, newInterval); //将newInterval插入intervals中 int low = intervals[0][0], high = intervals[0][1]; for(int i=1; i<intervals.length; i++){ if(intervals[i][0] > high){ int[] temp = new int[2]; temp[0] = low; temp[1] = high; list.add(temp); low = intervals[i][0]; high = intervals[i][1]; } else{ high = Math.max(high, intervals[i][1]); } } int[] temp = new int[2]; temp[0] = low; temp[1] = high; list.add(temp); int[][] res = new int[list.size()][2]; for(int i=0; i<list.size(); i++){ res[i] = list.get(i); } return res; } //将newInterval插入intervals中 public int[][] insertIntervals(int[][] intervals, int[] newInterval){ int[][] res = new int[intervals.length+1][2]; boolean flag = false;//是否被插入 int j=0; for(int i=0; i<intervals.length; i++){ if(!flag && intervals[i][0] > newInterval[0]){ res[j++] = newInterval; res[j++] = intervals[i]; flag = true; } else{ res[j++] = intervals[i]; } } if(!flag){ //还没有插入 res[j++] = newInterval; } return res; } }