专栏：50多种数据结构彻底征服
专栏：50多种经典图论算法全部掌握
2025年 1 月 15 日马斯克在X(以前的推特)上发文称：他们招聘软件工程师不关心你的学历，或者你是否上过大学以及是否在哪个大厂工作过，只需要展示你的代码即可。不过我感觉这不是很靠谱，因为读代码要比看简历难多了，发给你一份代码要看到啥时候，并且看代码还需要专业的人才能看，hr不一定看的懂，现在很多hr连简历都看不过来，直接使用筛选功能。不过这也给那些学历不高但能力很强的人更多的机会。
--------------下面是今天的算法题--------------
来看下今天的算法题，这题是LeetCode的第57题：插入区间。
问题描述
来源：LeetCode第57题
难度：中等
给你一个无重叠的，按照区间起始端点排序的区间列表 intervals，其中 intervals[i] = [starti, endi] 表示第 i 个区间的开始和结束，并且 intervals 按照 starti 升序排列。同样给定一个区间 newInterval = [start, end] 表示另一个区间的开始和结束。
在 intervals 中插入区间 newInterval，使得 intervals 依然按照 starti 升序排列，且区间之间不重叠（如果有必要的话，可以合并区间）。返回插入之后的 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 <= 10^4
intervals[i].length == 2
0 <= starti <= endi <= 10^5
intervals 根据 starti 按 升序 排列
newInterval.length == 2
0 <= start <= end <= 10^5
问题分析
这题说的是原来的区间是按照起始点排序的，且区间没有重叠。让我们在原来的区间插入一个新的区间，如果有重叠就把他们合并，如下图所示，因为区间[1,3]和区间[2,5]有重叠，
这里要判断要合并的区间和上面的哪些区间有重叠，因为上面的区间都已经按照起始点排序了，如果 当前区间的终点小于合并区间的起始点， 他们是没有重叠的 ，或者 当前区间的起始点大于合并区间的终点 ，他们也是没有重叠的。
没有重叠的区间只需要单独保存下来，有重叠的区间需要合并。
JAVA：
public int[][] insert(int[][] intervals, int[] newInterval) { List
ans = new ArrayList<>(); for (int[] interval : intervals) { if (newInterval == null || interval[1] < newInterval[0]) { // 前面单独的添加进来，或者已经合并完了，把后面的添加进来 ans.add(interval); } else if (interval[0] > newInterval[1]) { ans.add(newInterval);// 后面单独的区间。 ans.add(interval); newInterval = null; } else {// 合并区间 newInterval[0] = Math.min(newInterval[0], interval[0]); newInterval[1] = Math.max(newInterval[1], interval[1]); } } // 如果合并之后的区间没有保存下来，要保存下来 if (newInterval != null) ans.add(newInterval); return ans.toArray(new int[ans.size()][]); }
C++：
public: vector
> insert(vector
> &intervals, vector
&newInterval) { vector
> res; bool finish = false;// 合并完了，后面的不需要再合并了，直接添加 for (auto const &interval: intervals) { if (finish || interval[1] < newInterval[0]) { res.emplace_back(interval);// 前面单独 } else if (interval[0] > newInterval[1]) {// 后面单独 res.emplace_back(newInterval); res.emplace_back(interval); finish = true; } else {// 有交叉，合并 newInterval[0] = min(newInterval[0], interval[0]);//get min newInterval[1] = max(newInterval[1], interval[1]);//get max } } if (!finish) res.emplace_back(newInterval); return res; }
Python：
def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]: ans = [] for interval in intervals: if not newInterval or interval[1] < newInterval[0]: # 前面单独的添加进来，或者已经合并完了，把后面的添加进来 ans.append(interval) elif interval[0] > newInterval[1]: ans.append(newInterval[:]) # 后面单独的区间。 ans.append(interval) newInterval.clear() else: # 合并区间 newInterval[0] = min(newInterval[0], interval[0]) newInterval[1] = max(newInterval[1], interval[1]) # 如果合并之后的区间没有保存下来，要保存下来 if newInterval: ans.append(newInterval) return ans笔者简介
博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以 下载我整理的1000多页的PDF算法文档 。
热门跟贴