• Time:O(n)
• Space:O(n)

## C++

``````class Solution {
public:
vector<vector<int>> insert(vector<vector<int>>& intervals,
vector<int>& newInterval) {
const int n = intervals.size();
vector<vector<int>> ans;
int i = 0;

while (i < n && intervals[i][1] < newInterval[0])
ans.push_back(intervals[i++]);

// merge overlapping intervals
while (i < n && intervals[i][0] <= newInterval[1]) {
newInterval[0] = min(newInterval[0], intervals[i][0]);
newInterval[1] = max(newInterval[1], intervals[i][1]);
++i;
}

ans.push_back(newInterval);

while (i < n)
ans.push_back(intervals[i++]);

return ans;
}
};
``````

## JAVA

``````class Solution {
public int[][] insert(int[][] intervals, int[] newInterval) {
final int n = intervals.length;
List<int[]> ans = new ArrayList<>();
int i = 0;

while (i < n && intervals[i][1] < newInterval[0])

while (i < n && intervals[i][0] <= newInterval[1]) {
newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
++i;
}

while (i < n)

return ans.toArray(new int[ans.size()][]);
}
}
``````

## Python

``````class Solution:
def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
n = len(intervals)
ans = []
i = 0

while i < n and intervals[i][1] < newInterval[0]:
ans.append(intervals[i])
i += 1

while i < n and intervals[i][0] <= newInterval[1]:
newInterval[0] = min(newInterval[0], intervals[i][0])
newInterval[1] = max(newInterval[1], intervals[i][1])
i += 1

ans.append(newInterval)

while i < n:
ans.append(intervals[i])
i += 1

return ans
``````