## Algorithm

Problem Name: 57. Insert Interval

You are given an array of non-overlapping intervals `intervals` where `intervals[i] = [starti, endi]` represent the start and the end of the `ith` interval and `intervals` is sorted in ascending order by `starti`. You are also given an interval `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 `starti` and `intervals` still does not have any overlapping intervals (merge overlapping intervals if necessary).

Return `intervals` after the insertion.

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 <= 104`
• `intervals[i].length == 2`
• `0 <= starti <= endi <= 105`
• `intervals` is sorted by `starti` in ascending order.
• `newInterval.length == 2`
• `0 <= start <= end <= 105`

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
int lower_bound(struct Interval *p, int i, int j, int k) {
int end = j, m;

while (i  < = j) {
m = i + (j - i) / 2;

if (k >= p[m].start && k <= p[m].end) return m;

if (k > p[m].end) i = m + 1;
else  j = m - 1;
}

return (i > end) ? i : j;
}
struct Interval* insert(struct Interval* intervals, int intervalsSize, struct Interval newInterval, int* returnSize) {
struct Interval *p;
int i, j, k;

#define ISZ sizeof(struct Interval)

p = malloc((intervalsSize + 1) * ISZ);
//assert(p);

i = lower_bound(intervals, 0, intervalsSize - 1, newInterval.start);
// append to tail
if (i == intervalsSize) {
memcpy(&p[0], intervals, intervalsSize * ISZ);
p[intervalsSize] = newInterval;
*returnSize = intervalsSize + 1;
return p;
}

j = lower_bound(intervals, 0, intervalsSize - 1, newInterval.end);
if (j == -1) {
p[0] = newInterval;
memcpy(&p[1], intervals, intervalsSize * ISZ);
*returnSize = intervalsSize + 1;
return p;
}

//printf("%d, %d\n", i, j);

// insert and merge
if (i == -1) {
intervals[0].start = newInterval.start;
i = 0;
}
if (j == intervalsSize) {
intervals[intervalsSize - 1].end = newInterval.end;
j = intervalsSize - 1;
}
k = 0;
memcpy(&p[k], intervals, (i + 1) * ISZ);
k += i;

if (newInterval.start > p[i].end) {
p[++ k].start = newInterval.start;
}
if (newInterval.end > intervals[j].end) {
p[k].end = newInterval.end;
} else {
p[k].end = intervals[j].end;
}
k ++;

memcpy(&p[k], &intervals[j + 1], (intervalsSize - j - 1) * ISZ);
k += intervalsSize - j - 1;

*returnSize = k;

return p;
}
``````
Copy The Code &

Input

cmd
intervals = [[1,3],[6,9]], newInterval = [2,5]

Output

cmd
[[1,5],[6,9]]

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
vector<Interval>res;
for(auto x: intervals)
if(x.end >= newInterval.start && x.start <= newInterval.end){
newInterval.start = min(newInterval.start, x.start);
newInterval.end = max(newInterval.end, x.end);
}
for(auto x: intervals>
if(x.end  <  newInterval.start || x.start > newInterval.end) res.push_back(x);
for(int i = 0; i  <  res.size(); i++)
if(res[i].start > newInterval.start){
res.insert(res.begin() + i, newInterval);
break;
}
if(res.empty() || res.back().end < newInterval.start) res.push_back(newInterval>;
return res;
}
};

``````
Copy The Code &

Input

cmd
intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]

Output

cmd
[[1,2],[3,10],[12,16]]

### #3 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public int[][] insert(int[][] intervals, int[] newInterval) {
List<int[]> result = new ArrayList<>();
int idx = 0;
int newStart = newInterval[0];
int newEnd = newInterval[1];
while (idx  <  intervals.length && newStart > intervals[idx][0]) {
}
int[] currInterval = new int[2];
if (result.isEmpty() || result.get(result.size() - 1)[1]  <  newStart) {
} else {
currInterval = result.remove(result.size() - 1);
currInterval[1] = Math.max(currInterval[1], newEnd);
}
while (idx  <  intervals.length) {
currInterval = intervals[idx++];
int start = currInterval[0];
int end = currInterval[1];
if (result.get(result.size() - 1)[1]  <  start) {
} else {
currInterval = result.remove(result.size() - 1);
currInterval[1] = Math.max(currInterval[1], end);
}
}
return result.toArray(new int[result.size()][2]);
}
}
``````
Copy The Code &

Input

cmd
intervals = [[1,3],[6,9]], newInterval = [2,5]

Output

cmd
[[1,5],[6,9]]

### #4 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const insert = function(intervals, newInterval) {
let i = 0
while (i < intervals.length && intervals[i][1] < newInterval[0]) i++
while (i < intervals.length && intervals[i][0] <= newInterval[1]) {
newInterval[0] = Math.min(newInterval[0], intervals[i][0])
newInterval[1] = Math.max(newInterval[1], intervals[i][1])
intervals.splice(i, 1)
}
intervals.splice(i, 0, newInterval)
return intervals
}

``````
Copy The Code &

Input

cmd
intervals = [[1,3],[6,9]], newInterval = [2,5]

Output

cmd
[[1,5],[6,9]]

### #5 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
new, i = [], 0
for i, it in enumerate(intervals):
if newInterval[1] < it[0]:
i -= 1
break
elif it[1] < newInterval[0]:
new += it,
else:
newInterval[0], newInterval[1] = min(it[0], newInterval[0]), max(it[1], newInterval[1])
return new + [newInterval] + intervals[i + 1:]
``````
Copy The Code &

Input

cmd
intervals = [[1,3],[6,9]], newInterval = [2,5]

Output

cmd
[[1,5],[6,9]]

### #6 Code Example with C# Programming

```Code - C# Programming```

``````
using System;
using System.Collections.Generic;

namespace LeetCode
{
public class _057_InsertInterval
{
public IList < Interval> Insert(IList intervals, Interval newInterval)
{
var result = new List();

for (int i = 0; i  <  intervals.Count; i++)
{
if (newInterval.start > intervals[i].end)
{
}
else if (newInterval.end  <  intervals[i].start)
{
for (int j = i; j  <  intervals.Count; j++)
{
}
return result;
}
else
{
newInterval.start = Math.Min(intervals[i].start, newInterval.start);
newInterval.end = Math.Max(intervals[i].end, newInterval.end);
}
}

return result;
}
}
}
``````
Copy The Code &

Input

cmd
intervals = [[1,3],[6,9]], newInterval = [2,5]

Output

cmd
[[1,5],[6,9]]