solution.md

# 插入区间
<p>给你一个<strong> 无重叠的</strong><em> ，</em>按照区间起始端点排序的区间列表。</p>
<p>在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。</p>
<p> </p>
<p><strong>示例 1：</strong></p>
<pre><strong>输入：</strong>intervals = [[1,3],[6,9]], newInterval = [2,5]<strong><br />输出：</strong>[[1,5],[6,9]]</pre>
<p><strong>示例 2：</strong></p>
<pre><strong>输入：</strong>intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]<strong><br />输出：</strong>[[1,2],[3,10],[12,16]]<strong><br />解释：</strong>这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。</pre>
<p><strong>示例 3：</strong></p>
<pre><strong>输入：</strong>intervals = [], newInterval = [5,7]<strong><br />输出：</strong>[[5,7]]</pre>
<p><strong>示例 4：</strong></p>
<pre><strong>输入：</strong>intervals = [[1,5]], newInterval = [2,3]<strong><br />输出：</strong>[[1,5]]</pre>
<p><strong>示例 5：</strong></p>
<pre><strong>输入：</strong>intervals = [[1,5]], newInterval = [2,7]<strong><br />输出：</strong>[[1,7]]</pre>
<p> </p>
<p><strong>提示：</strong></p>
<ul>
    <li><code>0 <= intervals.length <= 10<sup>4</sup></code></li>
    <li><code>intervals[i].length == 2</code></li>
    <li><code>0 <= intervals[i][0] <= intervals[i][1] <= 10<sup>5</sup></code></li>
    <li><code>intervals</code> 根据 <code>intervals[i][0]</code> 按 <strong>升序</strong> 排列</li>
    <li><code>newInterval.length == 2</code></li>
    <li><code>0 <= newInterval[0] <= newInterval[1] <= 10<sup>5</sup></code></li>
</ul>
<p>以下错误的选项是？</p>
## aop
### before
```cpp
#include <bits/stdc++.h>
using namespace std;
```
### after
```cpp

```

## 答案
```cpp
class Solution
{
public:
    vector<vector<int>> insert(vector<vector<int>> &intervals, vector<int> &newInterval)
    {
        intervals.push_back(newInterval);
        sort(intervals.begin(), intervals.end());
        int n = intervals.size();
        vector<vector<int>> 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<vector<int>> insert(vector<vector<int>> &intervals, vector<int> &newInterval)
    {
        if (intervals.size() == 0)
            return {newInterval};
        vector<vector<int>> 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<vector<int>> insert(vector<vector<int>> &intervals, vector<int> &newInterval)
    {
        if (newInterval.empty())
            return intervals;
        else if (intervals.empty())
        {
            intervals.push_back(newInterval);
            return intervals;
        }
        vector<vector<int>> 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<vector<int>> insert(vector<vector<int>> &intervals, vector<int> &newInterval)
    {
        if (intervals.empty())
        {
            intervals.push_back(newInterval);
            return intervals;
        }
        int n = intervals.size();
        int i = 0, j = n - 1;
        vector<vector<int>> 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;
    }
};
```