插入区间
-
给你一个 无重叠的 ，按照区间起始端点排序的区间列表 intervals，其中 intervals[i] = [starti, endi] 表示第 i 个区间的开始和结束，并且 intervals 按照 starti 升序排列。同样给定一个区间 newInterval = [start, end] 表示另一个区间的开始和结束。
-
在 intervals 中插入区间 newInterval，使得 intervals 依然按照 starti 升序排列，且区间之间不重叠（如果有必要的话，可以合并区间）。
-
返回插入之后的 intervals。
注意 你不需要原地修改 intervals。你可以创建一个新数组然后返回它。
示例 1：
输入：intervals = [[1,3],[6,9]], newInterval = [2,5]
输出：[[1,5],[6,9]]
解题思路
需要将 newInterval 插入到有序且无重叠的区间列表 intervals 中，并且在插入之后仍保持区间的无重叠和有序特性。
- 1、遍历 intervals，将所有在 newInterval 之前的区间直接加入结果列表 result(在之前的是不会有交集的)。
- 2、检查是否有需要合并的区间：
-
如果当前区间与 newInterval 有重叠，则合并它们，更新 newInterval 的起始和结束位置。 -
如果当前区间不再与 newInterval 重叠，说明 newInterval 应该插入在当前位置之前，将 newInterval 加入 result，然后继续将当前及之后的区间加入 result。 - 3、如果遍历完所有区间后 newInterval 仍未被插入，则将 newInterval 加入 result。
Java实现
public class InsertInterval {public int[][] insert(int[][] intervals, int[] newInterval) {List<int[]> result = new ArrayList<>();int i = 0;int n = intervals.length;// 添加所有在 newInterval 之前的区间（没有交集的前半部分）while (i < n && intervals[i][1] < newInterval[0]) {result.add(intervals[i]);i++;}// 合并重叠的区间while (i < n && intervals[i][0] <= newInterval[1]) {//找到最后一个合并的区间newInterval[0] = Math.min(newInterval[0], intervals[i][0]);newInterval[1] = Math.max(newInterval[1], intervals[i][1]);i++;}//加入合并后的区间result.add(newInterval);// 添加newInterval之后的区间（没有交集的后半部分）while (i < n) {result.add(intervals[i]);i++;}return result.toArray(new int[result.size()][]);}public static void main(String[] args) {InsertInterval insertInterval = new InsertInterval();int[][] intervals1 = {{1, 3}, {6, 9}};int[] newInterval1 = {2, 5};int[][] result1 = insertInterval.insert(intervals1, newInterval1);// 输出: [[1, 5], [6, 9]]for (int[] interval : result1) {System.out.println("[" + interval[0] + ", " + interval[1] + "]");}System.out.println("--------------------------------------" );int[][] intervals2 = {{1, 2}, {3, 5}, {6, 7}, {8, 10}, {12, 16}};int[] newInterval2 = {4, 9};int[][] result2 = insertInterval.insert(intervals2, newInterval2);// 输出: [[1, 2], [3, 10], [12, 16]]for (int[] interval : result2) {System.out.println("[" + interval[0] + ", " + interval[1] + "]");}}
}时间空间复杂度
- 时间复杂度: O(n)，其中 n 是区间数组 intervals 的长度。需遍历一次 intervals。
- 空间复杂度: O(n)，用于存储结果列表 result。新数组 result 包含最多 intervals.length + 1 个区间。