Java Solution with Comments: O(n)
The approach is to:\n1. Skip all the intervals that end before the newInterval starts because they would not overlap anyway. So we add them to the final result.
The approach is to:\n1. Skip all the intervals that end before the newInterval starts because they would not overlap anyway. So we add them to the final result.\n2. For those intervals that overlap with the newInterval, we will merge them before inserting into the final result list. We say that an interval b overlaps with a is b.start <= a.end.\n3. At the end, we will add the remaining intervals from the original array that do not overlap with the newInterval.\n\nWe will use a List since we do not know the size of our merged intervals beforehand and then we will convert the list to the required 2-dimensional array\n\n```\n    public int[][] insert(int[][] intervals, int[] newInterval) {\n        int n = intervals.length; // length of intervals\n        if (intervals == null || n == 0) {\n            return new int[][] { newInterval };\n        }\n        \n        // result list to be converted to int[] at the end\n        List<int[]> result = new ArrayList<>();\n        \n        // skip the intervals that end before new interval\n        int i = 0;\n        \n        while (i < n && intervals[i][1] < newInterval[0]) {\n            result.add(intervals[i]);\n            i++;\n        }\n        \n        // merge all intervals that overlap with newInterval\n        while (i < n && intervals[i][0] <= newInterval[1]) {\n            newInterval[0] = Math.min(intervals[i][0], newInterval[0]);\n            newInterval[1] = Math.max(intervals[i][1], newInterval[1]);\n            i++;\n        }\n        \n        // add the newly merged interval\n        result.add(newInterval);\n        \n        // add all the remaining intervals to result\n        while (i < n) {\n            result.add(intervals[i]);\n            i++;\n        }\n\n\t\t// convert to a 2d array\n        return result.toArray(new int[result.size()][2]);\n    }\n\t
['Array', 'Java']