阅读目录
- 1. 题目
- 2. 解题思路
- 3. 代码实现
1. 题目
2. 解题思路
第一步,我们先寻找新区间和原始区间列表的重叠部分。
假设新区间为 [ x 1 , x 2 ] [x_1, x_2] [x1,x2],原始区间列表中的其中一个区间为 [ y 1 , y 2 ] [y_1, y_2] [y1,y2],那么如果两个区间不存在重叠的话,如上图所示,当且仅当:
x 2 < y 1 ∣ ∣ y 2 < x 1 x_2 < y_1 \space || \space y_2 < x_1 x2<y1 ∣∣ y2<x1
其它情况下,两个区间都会存在重叠,而重叠后的新区间有:
x
1
n
e
w
=
m
i
n
(
x
1
,
y
1
)
x^{new}_1 = min(x_1, y_1)
x1new=min(x1,y1)
x
2
n
e
w
=
m
a
x
(
x
2
,
y
2
)
x^{new}_2 = max(x_2, y_2)
x2new=max(x2,y2)
因此,我们首先遍历一遍原始区间列表,如果某个区间和新区间不重叠,我们直接添加这个区间到结果区间列表中去,如果某个区间和新区间存在重叠,那么我们更新重叠区间。
然后,我们遍历结果区间列表,将重叠区间插入到合适的位置即可。
时间复杂度为 O ( n ) O(n) O(n),空间复杂度为 O ( n ) O(n) O(n)。
3. 代码实现
class Solution {
public:
vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
vector<vector<int> > new_intervals;
for (size_t i = 0; i < intervals.size(); ++i) {
// 和新区间不重叠,直接插入到结果中去
if (newInterval[1] < intervals[i][0] || intervals[i][1] < newInterval[0]) {
new_intervals.push_back(intervals[i]);
}
// 和新区间有重叠,更新重叠区间
else {
newInterval[0] = min(intervals[i][0], newInterval[0]);
newInterval[1] = max(intervals[i][1], newInterval[1]);
}
}
if (new_intervals.empty()) {
new_intervals.push_back(newInterval);
} else {
// 寻找新区间的插入位置
for (size_t i = 0; i < new_intervals.size(); ++i) {
// 比某个区间的起始位置小,插入到这个区间前面
if (newInterval[1] < new_intervals[i][0]) {
new_intervals.insert(new_intervals.begin()+i, newInterval);
break;
} // 插入到最后面
else if (i == new_intervals.size()-1 && newInterval[0] > new_intervals[i][1]) {
new_intervals.push_back(newInterval);
}
}
}
return new_intervals;
}
};