# Short, simple, O(n), in-place, Java solution with explanation

• The idea is to look at each interval in the list. If it intersects with newInterval then merge it to newInterval and delete it. In the end add newInterval back to its corresponding place.

``````public class Solution {
public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
ListIterator<Interval> i = intervals.listIterator();
Interval in;
while (i.hasNext()) {
in = i.next();
if (newInterval.end < in.start) {
i.previous();
break;
}
if (in.start <= newInterval.end && newInterval.start <= in.end) {
newInterval.start = Math.min(newInterval.start, in.start);
newInterval.end = Math.max(newInterval.end, in.end);
i.previous();
i.remove();
}
}
return intervals;
}
}``````

• ``````public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
ListIterator<Interval> i = intervals.listIterator();
Interval in;
while (i.hasNext()) {
in = i.next();
if (in.end<newInterval.start) {
continue;
}
if (in.start <= newInterval.end) {
newInterval = new Interval(Math.min(newInterval.start, in.start),
Math.max(newInterval.end, in.end));
i.remove();
} else {
i.previous();
break;
}
}
return intervals;
}``````

• beautiful and concise! i really need to make it right when using remove() and privious()/next() of ListIterator.

• ``````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 { //update t
t.start=min(t.start, intervals[i].start);
t.end=max(t.end, intervals[i].end);
}
}