最近看到一个网友的吐槽。这个网友在瑞典做后端开发工作，已经两年多了，工作节奏轻松，几乎是类955，每天都在家办公。虽然工作不紧不慢，生活质量也很高，但问题来了，社交圈子太小，没什么人交流，渐渐地就觉得有些孤独。
算法题：插入区间
问题背景
intervals = [[1, 3], [6, 9]]
newInterval = [2, 5]
[[1, 5], [6, 9]]
思路分析
分三种情况来处理：
新区间完全在某些区间的前面，完全可以直接加到最前面。 新区间完全在某些区间的后面，直接加到最尾巴。 新区间会与现有区间有重叠，这时候就得进行合并了。
算法实现
import java.util.*;
public class InsertInterval {
public static int[][] insert(int[][] intervals, int[] newInterval) {
List<int[]> result = new ArrayList<>();
// Step 1: Add intervals before the new interval
int i = 0;
while (i < intervals.length && intervals[i][1] < newInterval[0]) {
result.add(intervals[i]);
i++;
}
// Step 2: Merge overlapping intervals
while (i < intervals.length && 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);
// Step 3: Add intervals after the new interval
while (i < intervals.length) {
result.add(intervals[i]);
i++;
}
// Convert list to array
return result.toArray(new int[result.size()][]);
}
public static void main(String[] args) {
int[][] intervals = {{1, 3}, {6, 9}};
int[] newInterval = {2, 5};
int[][] result = insert(intervals, newInterval);
// Print the result
System.out.println(Arrays.deepToString(result));
}
}
代码讲解
添加前面的区间：首先，我们遍历区间列表，直到遇到新区间开始时间大于某个现有区间的结束时间为止。这些区间是不会与新区间重叠的，因此我们可以直接将它们添加到结果列表中。 合并重叠区间：然后，我们检查哪些区间与新区间有重叠，如果有，就更新新区间的起始值和结束值。比如新区间的开始时间会变成原本新区间和当前区间开始时间的最小值，结束时间会变成它们的最大值。 添加后面的区间：最后，我们将剩余的区间（那些结束时间早于新区间起始时间的区间）加入到结果列表中。
运行结果
int[][] intervals = {{1, 3}, {6, 9}};
int[] newInterval = {2, 5};
[[1, 5], [6, 9]]
复杂度分析
时间复杂度：由于我们只需要遍历一次区间列表，所以时间复杂度是 O(n)，其中 n 是区间的数量。 空间复杂度：由于我们使用了一个额外的 List来存储结果，空间复杂度是 O(n)，其中 n 是区间的数量。
-END-
以上，就是今天的分享了，看完文章记得右下角给何老师点赞，也欢迎在评论区写下你的留言。
