# Insert Interval Problem Solution

Insert Interval Problem: 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 :

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

## Problem Solution In Python

``````class Solution(object):
def insert(self, intervals, newInterval):
# O(n)
left, right, s, e = [], [], newInterval.start, newInterval.end
for i in intervals:
if i.end < s: left.append(i)
elif i.start > e: right.append(i)
else: s, e = min(s, i.start), max(e, i.end)
return left + [Interval(s, e)] + right

# O(nlogn)
res = []
for i in sorted(intervals + [newInterval], key = lambda x: x.start):
if not res: res.append(i)
else:
if i.start <= res[-1].end: res[-1].end = max(res[-1].end, i.end)
else: res.append(i)
return res
``````

## Problem Solution In Java

``````public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
List<Interval> ans = new ArrayList<>();
int i = 0, start = 0, end = 0;
for (Interval e : intervals) {
if (e.end < newInterval.start)
else if (end == 0 && e.end >= newInterval.start){
if (e.start > newInterval.end) {
end = 1; start = 1;
} else {
newInterval.start = Math.min(e.start, newInterval.start);
newInterval.end = Math.max(e.end, newInterval.end);
end = 1;
}
} else if (start == 0 && e.start <= newInterval.end) {
newInterval.end = Math.max(e.end, newInterval.end);
} else {
if (start == 0) {
start = 1;
}
}
}
if (end == 0 || start == 0) {
return ans;
}
return ans;
}
``````

## Problem Solution In C++

``````class Solution {
public:
vector<Interval> insert(vector<Interval>& intervals, Interval t) {
vector<Interval> result;
int i=0;
for(i=0; i<intervals.size(); ++i) {
if(intervals[i].end<t.start)
result.push_back(intervals[i]);
else if(intervals[i].start > t.end){
result.push_back(t);
break;
}
else {
t.start=min(t.start, intervals[i].start);
t.end=max(t.end, intervals[i].end);
}
}