# Leetcode Insert Interval problem solution

In this Leetcode Insert Interval problem solution, we have 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.

## 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);
}
}
for(; i<intervals.size(); ++i){
result.push_back(intervals[i]);
}
return result;
}
};
```