内部网站 建设目标,新网站快速排名软件,长沙专业网站建设服务,成都网站制作软件题目
给你一个 无重叠的 #xff0c;按照区间起始端点排序的区间列表。
在列表中插入一个新的区间#xff0c;你需要确保列表中的区间仍然有序且不重叠#xff08;如果有必要的话#xff0c;可以合并区间#xff09;。
示例 1#xff1a;
输入#xff1a;intervals …题目
给你一个 无重叠的 按照区间起始端点排序的区间列表。
在列表中插入一个新的区间你需要确保列表中的区间仍然有序且不重叠如果有必要的话可以合并区间。
示例 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
输入intervals [], newInterval [5,7]
输出[[5,7]]示例 4
输入intervals [[1,5]], newInterval [2,3]
输出[[1,5]]示例 5
输入intervals [[1,5]], newInterval [2,7]
输出[[1,7]]提示
0 intervals.length 10^4intervals[i].length 20 intervals[i][0] intervals[i][1] 10^5intervals 根据 intervals[i][0] 按 升序 排列newInterval.length 20 newInterval[0] newInterval[1] 10^5 解答
源代码
class Solution {public int[][] insert(int[][] intervals, int[] newInterval) {// 将新区间插入得到新的二维数组int[][] input getNewIntervals(intervals, newInterval);// 对新的二维数组进行排序Arrays.sort(input, new Comparatorint[]() {public int compare(int[] n1, int[] n2) {return n1[0] - n2[0];}});Listint[] res new ArrayList();// 合并区间for (int[] arr : input) {if (res.size() 0 || arr[0] res.get(res.size() - 1)[1]) {res.add(arr);} else {res.get(res.size() - 1)[1] Math.max(res.get(res.size() - 1)[1], arr[1]);}}return res.toArray(new int[res.size()][]);}public int[][] getNewIntervals(int[][] intervals, int[] newInterval) {Listint[] input new ArrayList();for (int[] interval : intervals) {input.add(new int[]{interval[0],interval[1]});}input.add(newInterval);return input.toArray(new int[input.size()][]);}
}
总结
我个人感觉这题和 [56. 合并区间] 核心思想差不多就是多了个把新的区间插进去的步骤最后还是要把所有区间合并起来所以依然沿用合并区间的方法。
