# 插入区间
给你一个 无重叠的 ，按照区间起始端点排序的区间列表。
在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。
示例 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] 重叠。
示例 3：
输入：intervals = [], newInterval = [5,7]
输出：[[5,7]]
示例 4：
输入：intervals = [[1,5]], newInterval = [2,3]
输出：[[1,5]]
示例 5：
输入：intervals = [[1,5]], newInterval = [2,7]
输出：[[1,7]]
提示：
0 <= intervals.length <= 104intervals[i].length == 20 <= intervals[i][0] <= intervals[i][1] <= 105intervals 根据 intervals[i][0] 按 升序 排列newInterval.length == 20 <= newInterval[0] <= newInterval[1] <= 105
以下错误的选项是？
## aop
### before
```cpp
#include
using namespace std;
```
### after
```cpp
```
## 答案
```cpp
class Solution
{
public:
vector> insert(vector> &intervals, vector &newInterval)
{
intervals.push_back(newInterval);
sort(intervals.begin(), intervals.end());
int n = intervals.size();
vector> ans;
for (int i = 0; i < n; i++)
{
int l = intervals[i][0], r = intervals[i][1];
if (!ans.size())
ans.push_back({l, r});
else
ans.back()[1] = max(ans.back()[1], r);
}
return ans;
}
};
```
## 选项
### A
```cpp
class Solution
{
public:
vector> insert(vector> &intervals, vector &newInterval)
{
if (intervals.size() == 0)
return {newInterval};
vector> res;
int lpos = 0, rpos = 0;
for (int i = 0; i < intervals.size(); i++)
{
if (intervals[i][0] < newInterval[0])
lpos++;
if (intervals[i][1] < newInterval[1])
rpos++;
}
if (lpos > rpos)
{
return intervals;
}
if (rpos == 0)
{
if (intervals[rpos][0] > newInterval[1])
{
res.push_back(newInterval);
for (int i = 0; i < intervals.size(); i++)
{
res.push_back(intervals[i]);
}
}
else
{
res.push_back({newInterval[0], intervals[0][1]});
for (int i = 1; i < intervals.size(); i++)
{
res.push_back(intervals[i]);
}
}
}
else if (lpos == 0)
{
if (rpos == intervals.size())
{
res.push_back(newInterval);
}
else if (intervals[rpos][0] > newInterval[1])
{
res.push_back(newInterval);
for (int i = rpos; i < intervals.size(); i++)
{
res.push_back(intervals[i]);
}
}
else if (intervals[rpos][0] <= newInterval[1])
{
res.push_back({newInterval[0], intervals[rpos][1]});
for (int i = rpos + 1; i < intervals.size(); i++)
{
res.push_back(intervals[i]);
}
}
}
else
{
if (intervals[lpos - 1][1] >= newInterval[0] && rpos == intervals.size())
{
for (int i = 0; i < lpos - 1; i++)
{
res.push_back(intervals[i]);
}
res.push_back({intervals[lpos - 1][0], newInterval[1]});
}
else if (intervals[lpos - 1][1] < newInterval[0] && rpos == intervals.size())
{
for (int i = 0; i < lpos; i++)
{
res.push_back(intervals[i]);
}
res.push_back(newInterval);
}
else if (intervals[lpos - 1][1] >= newInterval[0] && intervals[rpos][0] <= newInterval[1])
{
for (int i = 0; i < lpos - 1; i++)
{
res.push_back(intervals[i]);
}
res.push_back({intervals[lpos - 1][0], intervals[rpos][1]});
for (int i = rpos + 1; i < intervals.size(); i++)
{
res.push_back(intervals[i]);
}
}
else if (intervals[lpos - 1][1] >= newInterval[0] && intervals[rpos][0] > newInterval[1])
{
for (int i = 0; i < lpos - 1; i++)
{
res.push_back(intervals[i]);
}
res.push_back({intervals[lpos - 1][0], newInterval[1]});
for (int i = rpos; i < intervals.size(); i++)
{
res.push_back(intervals[i]);
}
}
else if (intervals[lpos - 1][1] < newInterval[0] && intervals[rpos][0] > newInterval[1])
{
for (int i = 0; i <= lpos - 1; i++)
{
res.push_back(intervals[i]);
}
res.push_back({newInterval[0], newInterval[1]});
for (int i = rpos; i < intervals.size(); i++)
{
res.push_back(intervals[i]);
}
}
else if (intervals[lpos - 1][1] < newInterval[0] && intervals[rpos][0] <= newInterval[1])
{
for (int i = 0; i <= lpos - 1; i++)
{
res.push_back(intervals[i]);
}
res.push_back({newInterval[0], intervals[rpos][1]});
for (int i = rpos + 1; i < intervals.size(); i++)
{
res.push_back(intervals[i]);
}
}
}
return res;
}
};
```
### B
```cpp
class Solution
{
public:
vector> insert(vector> &intervals, vector &newInterval)
{
if (newInterval.empty())
return intervals;
else if (intervals.empty())
{
intervals.push_back(newInterval);
return intervals;
}
vector> res;
int i = 0;
while (i < intervals.size() && intervals[i][1] < newInterval[0])
{
res.push_back(intervals[i]);
i++;
}
while (i < intervals.size() && intervals[i][0] <= newInterval[1])
{
newInterval[0] = min(intervals[i][0], newInterval[0]);
newInterval[1] = max(intervals[i][1], newInterval[1]);
i++;
}
res.push_back(newInterval);
while (i < intervals.size())
{
res.push_back(intervals[i]);
i++;
}
return res;
}
};
```
### C
```cpp
class Solution
{
public:
vector> insert(vector> &intervals, vector &newInterval)
{
if (intervals.empty())
{
intervals.push_back(newInterval);
return intervals;
}
int n = intervals.size();
int i = 0, j = n - 1;
vector> ans;
for (i = 0; i < n; i++)
if (newInterval[0] <= intervals[i][1])
break;
for (j = n - 1; j >= 0; j--)
if (newInterval[1] >= intervals[j][0])
break;
if (i == n)
intervals.push_back(newInterval);
else if (j == -1)
intervals.insert(intervals.begin(), newInterval);
else if (i > j)
{
intervals.insert(intervals.begin() + i, newInterval);
}
else if (i == j)
{
intervals[i][0] = min(intervals[i][0], newInterval[0]);
intervals[i][1] = max(intervals[i][1], newInterval[1]);
}
else
{
int minN = min(intervals[i][0], newInterval[0]);
int maxN = max(intervals[j][1], newInterval[1]);
intervals.erase(intervals.begin() + i, intervals.begin() + j + 1);
intervals.insert(intervals.begin() + i, {minN, maxN});
}
return intervals;
}
};
```