Detailed solution in Python3/Go/Ts with O(n) time and space complexity
Intuition\n\nAs we iterate through the intervals we only need to merge intervals that overlap each other and insert our new interval if it ends before the next 
# Intuition\n\nAs we iterate through the intervals we only need to merge intervals that overlap each other and insert our new interval if it ends before the next iterated interval\n\n# Approach\n\nWe begin by creating an empty list which will contain our final **output**.\n\nIterate through all of the provided `intervals`. For each iterated interval:\n- If it begins after our new interval ends,\n    - Insert new interval to our **output**\n    - **Add** all remaining intervals from the current interval to our **output** container.\n    - **Exit** the loop by returning _the currently generated output._\n- If it ends before our new interval begins\n    - **Add** it directly to our **output**, as new interval does not need to be processed yet and is still yet to come somewhere in the future time intervals.\n- If it overlaps with our new interval\n    - **Redefine** new interval by taking the **minimum** of _compared beginnings_ as the **start** and the **maximum** of _compared beginnings_ as the **end**. _DO NOT INSERT IT YET!_\n\nNotice that after we **exit** out of our defined loop without hitting the **return** statement within our **first condition**, we have yet to **insert** our new interval to our **output**. So, before _returning_ the **output** at this point, have our _new interval_ inserted into the returned **output**.\n\n# Complexity\n- Time complexity: $$O(n)$$\n\n- Space complexity: $$O(n)$$\n\n# Code\n```python3 []\nclass Solution:\n    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:\n        # Initialize an output container\n        output = []\n\n        # Iterate through all intervals\n        for i in range(len(intervals)):\n            # If the new interval ends before the current interval\n            # - Append the new interval to the output\n            # - Append the rest of the remaining intervals to the output\n            # - Return the output\n            if newInterval[1] < intervals[i][0]:\n                output.append(newInterval)\n                return output + intervals[i:]\n            \n            # If the new interval begins after the current interval\n            # - Append the current interval to the output\n            elif newInterval[0] > intervals[i][1]:\n                output.append(intervals[i])\n\n            # If the new interval overlaps with the current interval\n            # merge intervals to create a new interval where\n            # - Interval begins at the earliest of beginnings\n            # - Interval ends at the latest of ends\n            #\n            # ! Do not add the new interval to the output just yet!\n            # ! Further merging may be required\n            else:\n                newInterval = [\n                    min(newInterval[0], intervals[i][0]),\n                    max(newInterval[1], intervals[i][1])\n                ]\n\n        # Add the new interval to the output if not added already\n        # ! No need for conditions as we would not reach this point otherwise\n        output.append(newInterval)\n\n        # Return the final output\n        return output\n```\n```Go []\nfunc insert(intervals [][]int, newInterval []int) [][]int {\n    // Initialize an output container\n    output := [][]int{}\n\n    // Iterate through all intervals\n    for i := 0; i < len(intervals); i++ {\n        if newInterval[1] < intervals[i][0] {\n            // If the new interval ends before the current interval\n            // - Append the new interval to the output\n            // - Append the rest of the remaining intervals to the output\n            // - Return the output\n            output = append(output, newInterval)\n            return append(output, intervals[i:]...)\n        } else if newInterval[0] > intervals[i][1] {\n            // If the new interval begins after the current interval\n            // - Append the current interval to the output\n            output = append(output, intervals[i])\n        } else {\n            // If the new interval overlaps with the current interval\n            // merge intervals to create a new interval where\n            // - Interval begins at the earliest of beginnings\n            // - Interval ends at the latest of ends\n            //\n            // ! Do not add the new interval to the output just yet!\n            // ! Further merging may be required\n            newInterval = []int {\n                min(newInterval[0], intervals[i][0]),\n                max(newInterval[1], intervals[i][1]),\n            }\n        }\n    }\n\n    // Add the new interval to the output if not added already\n    // ! No need for conditions as we would not reach this point otherwise\n    output = append(output, newInterval)\n\n    // Return the final output\n    return output\n}\n```\n```typescript []\nfunction insert(intervals: number[][], newInterval: number[]): number[][] {\n    // Initialize an output container\n    const output: number[][] = [];\n\n    // Iterate through all intervals\n    for(let i = 0; i < intervals.length; i++) {\n        // If the new interval ends before the current interval\n        // - Append the new interval to the output\n        // - Append the rest of the remaining intervals to the output\n        // - Return the output\n        if (newInterval[1] < intervals[i][0]) {\n            output.push(newInterval);\n            intervals.slice(i).forEach(interval => output.push(interval));\n            return output;\n        }\n\n        // If the new interval begins after the current interval\n        // - Append the current interval to the output\n        else if (newInterval[0] > intervals[i][1])\n            output.push(intervals[i])\n\n        // If the new interval overlaps with the current interval\n        // merge intervals to create a new interval where\n        // - Interval begins at the earliest of beginnings\n        // - Interval ends at the latest of ends\n        //\n        // ! Do not add the new interval to the output just yet!\n        // ! Further merging may be required\n        else\n            newInterval = [\n                Math.min(newInterval[0], intervals[i][0]),\n                Math.max(newInterval[1], intervals[i][1])\n            ];\n    }\n\n    // Add the new interval to the output if not added already\n    // ! No need for conditions as we would not reach this point otherwise\n    output.push(newInterval);\n\n    // Return the final output\n    return output;\n};\n```\n
['Go', 'TypeScript', 'Python3']