题目描述和要求
给定一个无重叠的、按照区间起始端点排序的区间列表 intervals，其中 intervals[i] = [starti, endi] 表示第 i 个区间的开始和结束。同样给定一个区间 newInterval = [start, end] 表示另一个区间的开始和结束。
在 intervals 中插入区间 newInterval，使得 intervals 依然按照 starti 升序排列，且区间之间不重叠（如果有必要的话，可以合并区间）。
返回插入之后的 intervals。
示例解释
示例 1：
输入：intervals = [[1,3],[6,9]], newInterval = [2,5]
输出：[[1,5],[6,9]]
解释：插入新区间 [2,5] 后，原区间 [1,3] 和 [6,9] 合并为 [1,5]。
示例 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,10]。
解题思路
我们可以对区间进行遍历，根据新区间与当前区间的关系进行合并。具体步骤如下：
- 初始化一个结果列表，用于存储合并后的区间。
- 遍历区间列表，如果当前区间的结束位置小于新区间的起始位置，则将当前区间加入结果列表。
- 如果当前区间的起始位置大于新区间的结束位置，则将新区间加入结果列表，并更新新区间为当前区间。
- 如果当前区间与新区间存在重叠，则更新新区间的起始位置为当前区间和新区间起始位置的较小值，更新新区间的结束位置为当前区间和新区间结束位置的较大值。
- 将最后的新区间加入结果列表。
- 返回结果列表。
算法实现
import java.util.ArrayList; import java.util.List; public class InsertInterval { public int[][] insert(int[][] intervals, int[] newInterval) { List<int[]> merged = new ArrayList<>(); int index = 0; int n = intervals.length; // 添加所有在新区间之前的区间 while (index < n && intervals[index][1] < newInterval[0]) { merged.add(intervals[index++]); } // 合并重叠的区间 while (index < n && intervals[index][0] <= newInterval[1]) { newInterval[0] = Math.min(newInterval[0], intervals[index][0]); newInterval[1] = Math.max(newInterval[1], intervals[index][1]); index++; } merged.add(newInterval); // 添加剩余的区间 while (index < n) { merged.add(intervals[index++]); } return merged.toArray(new int[merged.size()][]); } }
复杂度分析
- 时间复杂度：O(n)，其中 n 为区间的数量。遍历一次区间列表。
- 空间复杂度：O(n)，额外使用了一个列表存储合并后的区间。
测试和验证
编写测试用例对算法进行验证，确保其正确性和健壮性。
import java.util.Arrays; public class Main { public static void main(String[] args) { InsertInterval insertInterval = new InsertInterval(); int[][] intervals1 = {{1, 3}, {6, 9}}; int[] newInterval1 = {2, 5}; System.out.println(Arrays.deepToString(insertInterval.insert(intervals1, newInterval1))); // [[1,5],[6,9]] int[][] intervals2 = {{1, 2}, {3, 5}, {6, 7}, {8, 10}, {12, 16}}; int[] newInterval2 = {4, 8}; System.out.println(Arrays.deepToString(insertInterval.insert(intervals2, newInterval2))); // [[1,2],[3,10],[12,16]] } }
总结和拓展
本题通过对区间的遍历和合并操作，实现了对新区间的插入操作。算法思路清晰简单，在处理类似问题时是一个不错的选择。
除了当前算法，我们也可以考虑其他实现方式，例如使用二分查找来寻找新区间的插入位置，或者使用栈来辅助合并区间等方法。
参考资料
- 《力扣经典150题》
- LeetCode 官方网站
