【面试经典150 | 区间】插入区间

Tag

【模拟】【数组】

---

题目解读

给定一个含有多个无重叠区间的数组，并且数组已经按照区间开始值升序排序。在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。

---

题目来源

57. 插入区间

---

解题思路

数据量为 $10^4$，基本上需要时间复杂度为 $O(n)$ 或者 $O(nlogn)$的解题方法。

方法一：合并区间

将 newInterval 区间加入到数组 intervals 数组中，再对数组排序，接下来按照 228汇总区间进行解决。

实现代码

复杂度分析

时间复杂度：$O(nlogn)$，$n$ 为新的数组intervals长度。

空间复杂度为 $O(1)$。

方法二：模拟

第二种方法就是模拟，遍历 intervals，找到与 newInterval 区间重合的区间，合并重合的区间。需要注意边界的处理！

具体地，记当我们遍历到区间为 $[l_i,r_i]$，区间 newInterval 的左右端点分别为 $left$ 和 $right$：

• 如果 $r_i<left$，说明 $[l_i,r_i]$ 与新区间不重合并且位于新区间的左侧，此时可以直接将区间 $[l_i,r_i]$ 加入答案数组中；
• 如果 $l_i>right$，说明 $[l_i,r_i]$ 与新区间不重合并且位于新区间的左侧，此时可以直接将区间 $[l_i,r_i]$ 加入答案数组中；
• 其他情况下说明当前遍历的区间与新区间重合，我们需要进行合并操作，两个区间的合并也就是求交集操作，即两个区间左端点的最小值作为合并后区间的左端点，两个区间右端点的最大值作为合并后区间的右端点。

还有一种情况，新的区间在区间数组中第一个区间的左侧，或者位于最后一个区间的右侧，这时候我们可以在遍历区间数组的时候一并解决。

具体地，需要维护一个 bool 变量 isPlaced 表示需要合并的新数组是否已经放置在了合适的位置，该变量初始化为 false。在遍历数组区间的时候，如果新区间位于当前遍历的区间左侧即 $l_i>right$ 的情况：

• 且 isPlaced = false，则将新区间加入到答案数组中；
• 将当前遍历的区间加入到答案数组中。

如果遍历完毕区间数组，isPlaced = false，说明新区间位于区间数组最后一个区间的右侧，则直接将新区间加入到答案数组中。

实现代码

class Solution {
public:vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {vector<vector<int>> res;int l = newInterval[0];int r = newInterval[1];bool isPlaced = false;  // 新的区间是否已经安置好for (auto& inter : intervals) {if (inter[0] > r) {if (!isPlaced) {isPlaced = true;res.push_back({l, r});}res.push_back(inter);}else if (inter[1] < l) {res.push_back(inter);}else {l = min(inter[0], l);r = max(inter[1], r);}}if (!isPlaced) {res.push_back({l, r});}return res;}
};

复杂度分析

时间复杂度：$O(n)$，$n$ 为数组intervals的长度。

空间复杂度为：$O(1)$。

---

其他语言

方法一的其他语言已经在 【面试经典150 | 区间】合并区间 介绍过了，这里只贴出方法二的其他程序语言的解法。

python3

class Solution:def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:left, right = newIntervalisPlaced = Falseres = []for li, ri in intervals:if li > right:if not isPlaced:res.append([left, right])isPlaced = Trueres.append([li, ri])elif ri < left:res.append([li, ri])else:left = min(left, li)right = max(right, ri)if not isPlaced:res.append([left, right])return res

---

写在最后

如果文章内容有任何错误或者您对文章有任何疑问，欢迎私信博主或者在评论区指出 💬💬💬。

如果大家有更优的时间、空间复杂度方法，欢迎评论区交流。

最后，感谢您的阅读，如果感到有所收获的话可以给博主点一个 👍 哦。