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.

&nbsp;
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].


&nbsp;
Constraints:


	0 &lt;= intervals.length &lt;= 104
	intervals[i].length == 2
	0 &lt;= starti &lt;= endi &lt;= 105
	intervals is sorted by starti in ascending order.
	newInterval.length == 2
	0 &lt;= start &lt;= end &lt;= 105


class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:

        intervals.append(newInterval)
        intervals.sort(key=lambda x: x[0])

        result = []
        for interval in intervals:
            if not result or result[-1][1] < interval[0]:
                result.append(interval)
            else:
                result[-1][1] = max(result[-1][1],interval[1])

        return result
class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        if (newInterval == null || newInterval.length == 0) return intervals;
        
        List<int[]> merged = new LinkedList<>();
        int i = 0;
        // add not overlapping
        while (i < intervals.length && intervals[i][1] < newInterval[0]) {
            merged.add(intervals[i]);
            i++;
        }
        // add overlapping
        while (i < intervals.length && intervals[i][0] <= newInterval[1]) {
            newInterval[0] = Math.min(intervals[i][0], newInterval[0]);
            newInterval[1] = Math.max(intervals[i][1], newInterval[1]);
            i++;
        }
        merged.add(newInterval);
        // add rest
        while (i < intervals.length) {
            merged.add(intervals[i]);
            i++;
        }
        return merged.toArray(new int[merged.size()][]);
    }
}
class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        vector<vector<int>> output;
        int n = intervals.size();
        int i = 0;
        while(i < n){
            if(newInterval[1] < intervals[i][0]){
                output.push_back(newInterval);
                while(i < n){
                    output.push_back(intervals[i]);
                    i++;
                }
                return output;
            }
            else if(newInterval[0] > intervals[i][1]){
                output.push_back(intervals[i]);
                i++;
            }
            else{
                newInterval[0] = min(newInterval[0], intervals[i][0]);
                newInterval[1] = max(newInterval[1], intervals[i][1]);
                i++;
            }
        }
        output.push_back(newInterval);//think about it
        return output;
    }
};
var insert = function(intervals, newInterval) {
    //Edge case
    if (intervals.length === 0) {
        return [newInterval];
    }
	//Find the index to insert newIntervals
    let current = 0;
    while (current < intervals.length && intervals[current][0] < newInterval[0]) {
        current++;
    }
    intervals.splice(current, 0, newInterval);
	//If newInterval is not the last index, check the element behigh newInterval to see if merge is needed
    if (current !== intervals.length -1) {
        let pointer = current + 1;
        if (intervals[pointer][0] <= newInterval[1]) {
            while (pointer < intervals.length && intervals[pointer][0] <= newInterval[1]) {
                pointer++;
            }
            newInterval[1] = Math.max(newInterval[1], intervals[pointer - 1][1]);
            intervals.splice(current + 1, pointer - (current + 1));
        }
    }
	//If newInterval is not the first index, check the element berfore newInterval to see if merge is needed
    if (current !== 0) {
        if (intervals[current - 1][1] >= newInterval[0]) {
            newInterval[0] = intervals[current - 1][0];
            newInterval[1] = Math.max(newInterval[1], intervals[current - 1][1]);
            intervals.splice(current - 1, 1);
        }
    }
    return intervals;
};
Insert Interval