# Insert Interval

## [Insert Interval](https://leetcode.com/problems/insert-interval)

Given a set of *non-overlapping* intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

**Example 1:**

```

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]
```

**Example 2:**

```

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].
```

**Example 3:**

```

Input: intervals = [], newInterval = [5,7]
Output: [[5,7]]
```

**Example 4:**

```

Input: intervals = [[1,5]], newInterval = [2,3]
Output: [[1,5]]
```

**Example 5:**

```

Input: intervals = [[1,5]], newInterval = [2,7]
Output: [[1,7]]
```

**Constraints:**

* `0 <= intervals.length <= 104`
* `intervals[i].length == 2`
* `0 <= intervals[i][0] <= intervals[i][1] <= 105`
* `intervals` is sorted by `intervals[i][0]` in **ascending** order.
* `newInterval.length == 2`
* `0 <= newInterval[0] <= newInterval[1] <= 105`

## Solutions

### 🧠 Cpp

```cpp
class Solution
{
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval)
    {
        //input check
        if(intervals.empty())
            return {newInterval};

        vector<vector<int>> res;
        res.reserve(intervals.size() + 1);
        int a = newInterval[0], b = newInterval[1]; 

        //find interval that could be altered to contain newInterval
        auto iter = begin(intervals),
                    iter_end = end(intervals);
        for(;iter < iter_end; ++iter)
        {
            int &x1 = iter->at(0), &x2 = iter->at(1);

            //booster to find correct element
            if(a > x1 && a > x2 && next(iter) != iter_end)
            {
                res.emplace_back(*iter);
                continue;
            }
            break;
        }

        //return {*iter};
        //alter this interval or insert new before interval it
        {
            int &x1 = iter->at(0), &x2 = iter->at(1);

            //(x1,a,b,x2) fully included
            if( x1 <= a && b <= x2 )
                return intervals;
            //(a,x1,x2,b) fully included
            if( a <= x1 && x2 <= b )
            {
                *iter = newInterval;
            }
            else if( a == x2 )
            {
                x2 = b;
            }
            //(a,x1,b,x2)
            else if( a < x1  && x1 <= b )
            {
                x1 = a;
            }
            //(x1,a,x2,b)
            else if( a <= x2 && x2 < b)
            {
                x2 = b;
            }
            //(a,b,x1,x2) //we can insert a new interval right before iter
            else if(x1 >= b)
            {
                iter = intervals.insert(iter, newInterval);//insert whole interval at prev pos
            }
            else if(next(iter) == iter_end)
            {
                if(a <= x2)
                    x2 = b;
                else
                {
                    res.emplace_back(*iter);
                    iter = intervals.insert(iter_end, newInterval);
                }
            }

        }

        //return {*iter};


        //check that intervals after modified/inserted one are not overlaping
        a = iter->at(0), b = iter->at(1);
        iter_end = end(intervals);
        auto finish_iter = next(iter);

        if(finish_iter != iter_end)
        for(;next(finish_iter) != iter_end; finish_iter++)
        {
            int &x1 = finish_iter->at(0), &x2 = finish_iter->at(1);
            if(b == x1 ||  b <= x2)
            {
                break;
            }
            if( b < next(finish_iter)->at(0))   
            {
                break;
            }
        }

        //take right valur from last overlapping
        if(finish_iter != iter_end)
        {
            int &x1 = finish_iter->at(0), &x2 = finish_iter->at(1);
            if(b >= x1)
            {
                if(x2 > b)
                    iter->at(1) = x2;
                finish_iter++;
            }
        }

        //at this point we finished with our interval,
        //all other intervals after it is not overlapping
        res.emplace_back(*iter);
        for(;finish_iter != iter_end; finish_iter++)
            res.emplace_back(*finish_iter);


        return res;
    }
};
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://anton-veselskyi.gitbook.io/codding-problems-solutions/leetcode/medium/insert-interval.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.