插入区间
难度:
标签:
题目描述
给你一个 无重叠的 ，按照区间起始端点排序的区间列表 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]]
示例 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]重叠。
提示：
0 <= intervals.length <= 104intervals[i].length == 20 <= starti <= endi <= 105intervals根据starti按 升序 排列newInterval.length == 20 <= start <= end <= 105
代码结果
运行时间: 52 ms, 内存: 16.3 MB
/*
* 思路：
* 1. 使用 Stream API 处理 intervals，将区间分为三部分：
* - 完全在 newInterval 之前的区间
* - 完全在 newInterval 之后的区间
* - 与 newInterval 有重叠的区间
* 2. 合并重叠的区间并插入到结果中。
*/
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Solution {
public int[][] insert(int[][] intervals, int[] newInterval) {
List<int[]> result = new ArrayList<>();
// 添加所有在 newInterval 之前的区间
Arrays.stream(intervals)
.filter(interval -> interval[1] < newInterval[0])
.forEach(result::add);
// 合并重叠区间
int[] mergedInterval = Arrays.stream(intervals)
.filter(interval -> interval[0] <= newInterval[1] && interval[1] >= newInterval[0])
.reduce(newInterval, (a, b) -> new int[]{Math.min(a[0], b[0]), Math.max(a[1], b[1])});
result.add(mergedInterval);
// 添加所有在 newInterval 之后的区间
Arrays.stream(intervals)
.filter(interval -> interval[0] > newInterval[1])
.forEach(result::add);
return result.toArray(new int[result.size()][]);
}
}解释
方法:
这个题解的思路是将新区间插入到原区间列表中的合适位置，同时合并所有重叠的区间。具体步骤如下：
1. 先将所有小于新区间左端点的区间添加到答案中
2. 然后将所有与新区间重叠的区间与新区间合并
3. 将合并后的新区间添加到答案中
4. 最后将剩余大于新区间右端点的区间添加到答案中
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
在你的算法中，如何确保新插入区间后整个区间列表仍然保持排序？
▷🦆
你的解法中提到了合并重叠区间，能否详细解释什么情况下两个区间被视为重叠？
▷🦆
在合并重叠区间时，你选择了更新newInterval来代表合并后的区间。这样做有什么特别的优势吗？
▷🦆
如果新区间newInterval位于所有现有区间的最左端或最右端，你的算法处理流程会有什么不同吗？
▷相关问题
合并区间
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
示例 1：
输入：intervals = [[1,3],[2,6],[8,10],[15,18]] 输出：[[1,6],[8,10],[15,18]] 解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2：
输入：intervals = [[1,4],[4,5]] 输出：[[1,5]] 解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
提示：
1 <= intervals.length <= 104intervals[i].length == 20 <= starti <= endi <= 104
Range 模块
Range模块是跟踪数字范围的模块。设计一个数据结构来跟踪表示为 半开区间 的范围并查询它们。
半开区间 [left, right) 表示所有 left <= x < right 的实数 x 。
实现 RangeModule 类:
RangeModule()初始化数据结构的对象。void addRange(int left, int right)添加 半开区间[left, right)，跟踪该区间中的每个实数。添加与当前跟踪的数字部分重叠的区间时，应当添加在区间[left, right)中尚未跟踪的任何数字到该区间中。boolean queryRange(int left, int right)只有在当前正在跟踪区间[left, right)中的每一个实数时，才返回true，否则返回false。void removeRange(int left, int right)停止跟踪 半开区间[left, right)中当前正在跟踪的每个实数。
示例 1：
输入 ["RangeModule", "addRange", "removeRange", "queryRange", "queryRange", "queryRange"] [[], [10, 20], [14, 16], [10, 14], [13, 15], [16, 17]] 输出 [null, null, null, true, false, true] 解释 RangeModule rangeModule = new RangeModule(); rangeModule.addRange(10, 20); rangeModule.removeRange(14, 16); rangeModule.queryRange(10, 14); 返回 true （区间 [10, 14) 中的每个数都正在被跟踪） rangeModule.queryRange(13, 15); 返回 false（未跟踪区间 [13, 15) 中像 14, 14.03, 14.17 这样的数字） rangeModule.queryRange(16, 17); 返回 true （尽管执行了删除操作，区间 [16, 17) 中的数字 16 仍然会被跟踪）
提示：
1 <= left < right <= 109- 在单个测试用例中，对
addRange、queryRange和removeRange的调用总数不超过104次