**source:**https://leetcode.com/problems/insert-interval/**C/C++**

**Solution to LeetCode**problem

**57**.

**Insert Interval**.

## Problem

You are given an array of non-overlapping intervals `intervals`

where `intervals[i] = [start`

represent the start and the end of the _{i}, end_{i}]`i`

interval and ^{th}`intervals`

is sorted in ascending order by `start`

. You are also given an interval _{i}`newInterval = [start, end]`

that represents the start and end of another interval.

Insert `newInterval`

into `intervals`

such that `intervals`

is still sorted in ascending order by `start`

and _{i}`intervals`

still does not have any overlapping intervals (merge overlapping intervals if necessary).

Return * intervals after the insertion*.

## Examples

**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].

## Constraints

`0 <= intervals.length <= 10`

^{4}`intervals[i].length == 2`

`0 <= starti <= endi <= 10`

^{5}`intervals`

is sorted by start_{i}in ascending order.`newInterval.length == 2`

`0 <= start <= end <= 10`

^{5}

## Solution

- For this problem, we need to know if the
`newInterval`

array has been merged. - If has not been merged, we select what is the next array to merge:
`min(newInterval[0], intervals[i][0])`

- If our result array is empty, we just add the current array to it.
- Else:
- We determine if the current array fits inside the last one added to the result.
- If so, we do nothing with it and move to the next one.
- If not, we determine if the lower index fits inside the last one added.
- If yes, then we just set the upper index of the last one added to
`max(lastAdded[1], current[1])`

.

- If yes, then we just set the upper index of the last one added to
- If not, then we push the current array to the result.

- We finish once we added all the arrays and the new interval.

- We determine if the current array fits inside the last one added to the result.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

class Solution {
public:
vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
if (intervals.size() == 0)
return {newInterval};
vector<vector<int>> result;
bool newMerged = false;
bool isNewNext = false;
int i=0;
while (i < intervals.size() || !newMerged) {
isNewNext = false;
vector<int> *next = &intervals[i];
if ((!newMerged && i == intervals.size()) || (!newMerged && newInterval[0] <= intervals[i][0])) {
isNewNext = true;
next = &newInterval;
}
if (result.size() == 0)
result.push_back(*next);
else if ((*next)[0] >= result[result.size()-1][0] &&
(*next)[0] <= result[result.size()-1][1])
result[result.size()-1][1] = max((*next)[1], result[result.size()-1][1]);
else
result.push_back(*next);
if (isNewNext)
newMerged = true;
else
i++;
}
return result;
}
};